one line of code at a time

https://leetcode.com/problems/keys-and-rooms/ class Solution: def canVisitAllRooms(self, rooms: List[List[int]]) -> bool: keySet = set() keySet.add(0) visitedRooms = set() def dfs(currRoom, keySet): if currRoom not in keySet: return False visitedRooms.add(currRoom) for k in rooms[currRoom]: if k..

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..

그래프 문제인 것을 인식했다면, 5가지 알고리즘을 떠올리자.1. DFS2. BFS3. Union-Find4. Topological Sort5. Dijkstra's Algorithm 참고https://www.youtube.com/watch?v=utDu3Q7Flrw&list=PLot-Xpze53ldBT_7QA8NVot219jFNr_GI

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..

Quicksort is an efficient, comparison-based sorting algorithm that uses the divide-and-conquer approach. It works by selecting a 'pivot' element from the array, partitioning the other elements into two sub-arrays (those less than the pivot and those greater than the pivot), and recursively sorting the sub-arrays. The key steps are:Pick a pivot: Choose an element from the array. The choice of piv..

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: ..