one line of code at a time

https://leetcode.com/problems/letter-combinations-of-a-phone-number/ 각 숫자마다 designated letter들이 있다.digits가 "23"일 때 2에 있는 문자 a, b, c와 3에 있는 문자 d, e, f의 조합으로 몇 개의 letter combination을 만들 수 있는지 구하는 문제다. class Solution: def letterCombinations(self, digits: str) -> List[str]: res = [] digitsToChar = { "2": "abc", "3": "def", "4": "ghi", "5":..

https://leetcode.com/problems/island-perimeter/ class Solution(object): def islandPerimeter(self, grid): m, n = len(grid), len(grid[0]) perimeter = 0 nei_dict = {0: 4, 1: 3, 2: 2, 3: 1, 4: 0} for i in range(m): for j in range(n): if grid[i][j] == 1: # check neighbors nei = 0 directio..

https://leetcode.com/problems/word-search/ class Solution(object): def exist(self, board, word): m, n = len(board), len(board[0]) def dfs(idx, visited, r, c): if idx == len(word): return True visited.append((r, c)) directions = [(0, 1), (0, -1), (-1, 0), (1, 0)] for dr, dc in directions: nr, nc = r + dr, c..

https://leetcode.com/problems/find-eventual-safe-states 사이클이 생기면 safe node가 될 수 없다.그리고 그 사이클을 만드는 노드들은 모두 safe node가 될 수 없다.outgoing edge가 없는 terminal node는 safe node이다. if all the neighbors of its node is safe node, then that means it is also a safe node.그런데 이웃 노드가 safe node가 아니면, 그 노드도 safe 노드가 아니다. class Solution: def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]: n =..

https://leetcode.com/problems/find-the-town-judge/ town judge가 존재하는데 (1) town judge는 아무도 믿지 않는다. 그런데 (2) town judge를 제외한 모든 사람은 town judge를 믿는다. (1)과 (2) 조건을 만족하는 judge는 한 명이다. trust라는 배열이 주어지는데 여기에 없다면 관계는 존재하지 않는다. Input: n = 3, trust = [[1,3],[2,3]]Output: 3 이런 input이 있다면, 그 관계는 이렇게 표현할 수 있다.여기서 1과 2의 outdegree는 각각 1개이고, indegree는 없다.3을 보면, indegree는 2개 (n-1)이고, outdegree는 없다.town judge는 inde..

leetcode 100.same tree가 자식 노드가 같은지를 판단하는 것이었다면, 이 문제는 left child가 right child와 같은지 보면 된다. 대칭인지 확인하기 위해서는 left subtree와 right subtree를 가지고 동시에 dfs를 돌려야 한다. 시간 복잡도는 O(n)이다. 여기서 n은 the number of node.메모리 복잡도는 O(h)이고, h는 height of a tree. class Solution: def isSymmetric(self, root: Optional[TreeNode]) -> bool: def dfs(left, right): if not left and not right: ..

두 개의 이진트리가 있을 때 두 트리가 같은지 판단해야 한다. 트리의 구조가 같고 트리의 노드가 같은 값을 가질 때 두 개의 이진트리가 같다고 판단한다.  class Solution: def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool: def dfs(tree_a, tree_b): if not tree_a and not tree_b: return True if not tree_a or not tree_b: return False if tree_a.val != tree_b.val: ..

이진 트리의 inorder traversal class Solution: def dfs(self, root, answer): if root is None: return self.dfs(root.left, answer) answer.append(root.val) self.dfs(root.right, answer) def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]: answer = [] self.dfs(root, answer) return answer

https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/ 중간 노드를 삭제한 연결 리스트를 반환하는 문제다.  연결 리스트에서 중간 노드를 반환하는 건 slow, fast 이렇게 두 개의 포인터를 쓰면 된다. 그런데 이 문제에서는 중간 노드를 제거해야 한다.  연결리스트에서는 종종 head 앞에 가상의 노드를 하나 더 추가하면 쉽게 문제를 풀 수 있다.dummy 노드를 만들어준다.dummy = ListNode(next=head) 그런 다음에 slow 포인터를 dummy에 놓고, fast 포인터를 head에 놓는다.slow, fast = dummy, head leetcode 876번 중간 노드 찾기 문제에서는 slow, fast 둘 다 ..

https://leetcode.com/problems/middle-of-the-linked-list/description/ 연결리스트의 중간 지점을 구하는 문제이다. fast, slow 이렇게 두 개의 포인터를 활용하면 쉽게 중간 지점을 구할 수 있다. # Definition for singly-linked list.# class ListNode(object):# def __init__(self, val=0, next=None):# self.val = val# self.next = nextclass Solution(object): def middleNode(self, head): slow, fast = head, head while fas..