1
class Solution:
2
    def exist(self, board: List[List[str]], word: str) -> bool:
3
        n = len(board)
4
        m = len(board[0])
5
        st = [[False for _ in range (m)] for _ in range (n)]
6
        dx = [-1, 1, 0, 0]
7
        dy = [0, 0, -1, 1]
8
        def dfs(x, y, u) -> bool:
9
            if word[u] != board[x][y]:
10
                return False
11
            if u == len(word) - 1:
12
                return True
13
            st[x][y] = True
14
            ok = False
15
            for i in range(4):
16
                tx = x + dx[i]
17
                ty = y + dy[i]
18
                if tx < 0 or tx >= n or ty < 0 or ty >= m:
19
                    continue
20
                if st[tx][ty]:
21
                    continue
22
                ok |= dfs(tx, ty, u + 1)
23
            st[x][y] = False
24
            return ok
25

26

27
        for i in range(n):
28
            for j in range(m):
29
                if dfs(i, j, 0):
30
                    return True
31
        return False

1
class Solution:
2
    def generateParenthesis(self, n: int) -> List[str]:
3
        ans = []
4
        s = ['.' for _ in range (2 * n)]
5
        def dfs(u, left, right):
6
            if u == 2 * n:
7
                ans.append(''.join(s))
8
                return
9

10
            if left < n:
11
                s[u] = '('
12
                dfs(u + 1, left + 1, right)
13
                s[u] = '.'
14

15
            if right < left:
16
                s[u] = ')'
17
                dfs(u + 1, left, right + 1)
18
                s[u] = '.'
19

20
        dfs(0, 0, 0)
21
        return ans

1
class Solution:
2
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
3
        ans = []
4
        tmp = []
5

6
        def dfs(u, cur):
7
            if cur > target:
8
                return
9
            if cur == target:
10
                ans.append(tmp[:])
11
                return
12
            for i in range(u, len(candidates)):
13
                tmp.append(candidates[i])
14
                dfs(i, cur + candidates[i])
15
                tmp.pop()
16

17
        dfs(0, 0)
18
        return ans

1
class Solution:
2
    def letterCombinations(self, digits: str) -> List[str]:
3
        mapping = {2: 'abc', 3: 'def', 4: 'ghi', 5: 'jkl', 6: 'mno', 7: 'pqrs', 8: 'tuv', 9: 'wxyz'}
4
        ans = []
5
        n = len(digits)
6
        tmp = []
7

8
        def dfs(u):
9
            if u >= n:
10
                ans.append(''.join(tmp[:]))
11
                return
12
            letters = mapping[int(digits[u])]
13
            for letter in letters:
14
                tmp.append(letter)
15
                dfs(u + 1)
16
                tmp.pop()
17

18
        dfs(0)
19
        return ans

1
class Solution:
2
    def subsets(self, nums: List[int]) -> List[List[int]]:
3
        ans = []
4

5
        n = len(nums)
6
        tmp = []
7

8
        def dfs(u):
9
            if u >= n:
10
                ans.append(tmp[:])
11
                return
12

13
            dfs(u + 1)
14

15
            tmp.append(nums[u])
16
            dfs(u + 1)
17
            tmp.pop()
18

19
        dfs(0)
20
        return ans

1
class Solution:
2
    def permute(self, nums: List[int]) -> List[List[int]]:
3
        ans = []
4
        n = len(nums)
5

6
        tmp = []
7
        st = [False for _ in range(n)]
8
        def dfs(u):
9
            if u >= n:
10
                ans.append(tmp[:])
11
                return
12
            for i in range(n):
13
                if st[i]:
14
                    continue
15

16
                st[i] = True
17
                tmp.append(nums[i])
18

19
                dfs(u + 1)
20

21
                tmp.pop()
22
                st[i] = False
23

24
        dfs(0)
25
        return ans

1
class Node:
2
    __slots__ = 'son', 'end'
3

4
    def __init__(self):
5
        self.son = [None] * 26
6
        self.end = False
7

8
class Trie:
9

10
    def __init__(self):
11
        self.root = Node()
12

13
    def insert(self, word: str) -> None:
14
        cur = self.root
15
        for c in word:
16
            c = ord(c) - ord('a')
17
            if cur.son[c] is None:
18
                cur.son[c] = Node()
19
            cur = cur.son[c]
20
        cur.end = True
21

22
    def search(self, word: str) -> bool:
23
        cur = self.root
24
        for c in word:
25
            c = ord(c) - ord('a')
26
            if cur.son[c] is None:
27
                return False
28
            cur = cur.son[c]
29
        return cur.end
30

31
    def startsWith(self, prefix: str) -> bool:
32
        cur = self.root
33
        for c in prefix:
34
            c = ord(c) - ord('a')
35
            if cur.son[c] is None:
36
                return False
37
            cur = cur.son[c]
38
        return True

1
class Solution:
2
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
3
        e = [[] for _ in range(numCourses)]
4
        in_degree = [0 for _ in range(numCourses)]
5

6
        for edge in prerequisites:
7
            e[edge[1]].append(edge[0])
8
            in_degree[edge[0]] += 1
9

10
        q = deque([i for i in range(numCourses) if in_degree[i] == 0])
11
        visited = 0
12

13
        while q:
14
            u = q.popleft()
15
            visited += 1
16
            for v in e[u]:
17
                in_degree[v] -= 1
18
                if in_degree[v] == 0:
19
                    q.append(v)
20

21
        return visited == numCourses

1
class Solution:
2
    def orangesRotting(self, grid: List[List[int]]) -> int:
3
        n, m = len(grid), len(grid[0])
4

5
        for i in range(n):
6
            for j in range(m):
7
                if grid[i][j] == 0:
8
                    grid[i][j] = -1
9
                elif grid[i][j] == 1:
10
                    grid[i][j] = float("inf")
11
                else:
12
                    grid[i][j] = 0
13

14
        dx = [-1, 1, 0, 0]
15
        dy = [0, 0, -1, 1]
16
        q = deque()
17

18
        for i in range(n):
19
            for j in range(m):
20
                if grid[i][j] == 0:
21
                    q.append((i, j))
22

23
        while q:
24
            x, y = q.popleft()
25
            for i in range(4):
26
                tx = x + dx[i]
27
                ty = y + dy[i]
28
                if tx < 0 or tx >= n or ty < 0 or ty >= m:
29
                    continue
30
                if grid[tx][ty] < grid[x][y] + 1:
31
                    continue
32
                grid[tx][ty] = grid[x][y] + 1
33
                q.append((tx, ty))
34

35
        ans = 0
36
        for i in range(n):
37
            for j in range(m):
38
                if grid[i][j] == float("inf"):
39
                    return -1
40
                if grid[i][j] != -1:
41
                    ans = max(ans, grid[i][j])
42

43
        return ans

1
class Solution:
2
    def numIslands(self, grid: List[List[str]]) -> int:
3
        n, m = len(grid), len(grid[0])
4

5
        dx = [-1, 1, 0, 0]
6
        dy = [0, 0, -1, 1]
7
        def dfs(x, y):
8
            grid[x][y] = '0'
9
            for i in range(4):
10
                tx = x + dx[i]
11
                ty = y + dy[i]
12
                if tx < 0 or tx >= n or ty < 0 or ty >= m:
13
                    continue
14
                if grid[tx][ty] == '0':
15
                    continue
16
                dfs(tx, ty)
17

18
        ans = 0
19
        for i in range(n):
20
            for j in range(m):
21
                if grid[i][j] == '1':
22
                    ans += 1
23
                    dfs(i, j)
24

25
        return ans