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