recursion

22 Generate Parentheses

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        if n == 0:
            return []
        self.res = []
        self.solution('', n, n)
        return self.res
       
    def solution(self, s, left_n, right_n):
        if left_n == 0 and right_n == 0:
            self.res.append(s)
        if left_n > right_n or left_n < 0 or right_n < 0:
            return
        self.solution(s+'(', left_n - 1, right_n)
        self.solution(s+')', left_n, right_n - 1)

39 Combination Sum

'''
Example :
Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
  [7],
  [2,2,3]
]
'''
class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        if not candidates or not target:
            return []        
        res = []
        path = []        
        def dfs(candidates, target, tmp):
            if target < 0:
                return
            elif target == 0:
                res.append(tmp)
            else:
                for i in range(len(candidates)):
                    if candidates[i] <= target:
                        dfs(candidates[i:], target-candidates[i], tmp+[candidates[i]])       
                      
        dfs(candidates, target, [])
        return res

40 Combination Sum II

'''
Example :
Input: candidates = [10,1,2,7,6,1,5], target = 8,
A solution set is:
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]
'''
class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        if not candidates or not target:
            return []
        
        candidates = sorted(candidates)
        res = []
        path = []
        
        def dfs(candidates, target, tmp):
            if target < 0:
                return
            elif target == 0:
                if tmp not in res:
                    res.append(tmp)
            else:
                for i in range(len(candidates)):
                    if candidates[i] <= target:
                        dfs(candidates[i+1:], target-candidates[i], tmp+[candidates[i]])
        dfs(candidates, target, [])
        return res

46 Permutations

# 全排列
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        if len(nums) == 0:
            return []
        self.res = []
        self.used = [False] * len(nums)
        self._dfs(nums, 0, [])
        return self.res
    
    def _dfs(self, nums, index, tmp):
        if index == len(nums):
            self.res.append(tmp)
            return 
        
        for i in range(len(nums)):
            if not self.used[i]:
                self.used[i] = True
                self._dfs(nums, index+1, tmp+[nums[i]])
                self.used[i] = False

47 Permutations II

'''
Input: [1,1,2]
Output:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]
'''
class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        if len(nums) == 0:
            return []
        self.res = []
        self.used = [False] * len(nums)
        self._dfs(nums, 0, [])
        return self.res
    
    def _dfs(self, nums, index, tmp):
        if index == len(nums) and tmp not in self.res:
            self.res.append(tmp)
            return 
        
        for i in range(len(nums)):
            if not self.used[i]:
                self.used[i] = True
                self._dfs(nums, index+1, tmp+[nums[i]])
                self.used[i] = False

52 N-Queens II

class Solution:
    def totalNQueens(self, n: int) -> int:
        if n < 1:
            return 0
        self.count = 0
        self.cols = set()
        self.pie = set()
        self.na = set()
        self._dfs(n, 0)
        return self.count
    
    def _dfs(self, n, row):
        if row >= n:
            self.count += 1            
        for col in range(n):
            if col in self.cols or row+col in self.pie or row-col in self.na:
                continue
            self.cols.add(col)
            self.pie.add(row+col)
            self.na.add(row-col)
            self._dfs(n, row+1)
            self.cols.remove(col)
            self.pie.remove(row+col)
            self.na.remove(row-col)

55. Jump Game

'''
Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
'''
class Solution:
    def canJump(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        #贪心      
        # n = len(nums)
        # reach = 0
        # i = 0
        # while i <= reach and reach < n-1:
        #     reach = max(reach, nums[i] + i)
        #     i += 1
        # if reach >= n - 1:
        #     return True
        # else:
        #     return False
        
        #dp
        n = len(nums)
        dp = [0] * n
        dp[0] = 0
        
        for i in range(1, n):
            dp[i] = max(dp[i-1], nums[i-1]) - 1
            if dp[i] < 0:
                return False
        if dp[-1] >= 0:
            return True

67 Add Binary

'''
Example 1:

Input: a = "11", b = "1"
Output: "100"
Example 2:

Input: a = "1010", b = "1011"
Output: "10101"
'''
class Solution:
    # 递归
    def addBinary(self, a: str, b: str) -> str:
        if not a or not b:
            return a if a else b
        
        if a[-1] == '1' and b[-1] == '1':
            return self.addBinary(self.addBinary(a[:-1], b[:-1]), '1') + '0'
        elif a[-1] == '0' and b[-1] == '0':
            return self.addBinary(a[:-1], b[:-1]) + '0'
        else:
            return self.addBinary(a[:-1], b[:-1]) + '1'

77 Combinations

'''
Input: n = 4, k = 2
Output:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]
'''
class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        if n < 1:
            return []
        if k > n:
            return []        
        self.res = []
        self.dfs(n, k, 1, [])
        return self.res
    
    def dfs(self, n, k, start, tmp): #从start开始选，下次选只能选start后面的数
        if len(tmp) == k:
            self.res.append(tmp)
            return         
        for i in range(start, n+1):
            self.dfs(n, k, i+1, tmp+[i])

78 Subsets

'''
Input: nums = [1,2,3]
Output:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]
'''
class Solution(object):
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = []
        if len(nums) == 0:
            return res
        res.append([])
        for n in nums:
            temp = []
            for t in res:
                m = t + [n]
                temp.append(m)
            res = res + temp
        return res
#递归
class Solution(object):
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        if len(nums) == 0:
            return []
        res = []
        temp = []
        self.hs(nums, res, temp, 0)
        return res
    def hs(self, nums, res, temp, i):
        if i == len(nums):
            res.append(temp)
            return
        self.hs(nums, res, temp+[nums[i]], i+1)
        self.hs(nums, res, temp, i+1)

87 Scramble String

'''
Example 1:
Input: s1 = "great", s2 = "rgeat"
Output: true

Example 2:
Input: s1 = "abcde", s2 = "caebd"
Output: false
'''
class Solution:
    def isScramble(self, s1, s2):
        """
        :type s1: str
        :type s2: str
        :rtype: bool
        """
        if s1 == s2:
            return True
        if sorted(s1) != sorted(s2):
            return False
        length = len(s1)
        for i in range(1, length):
            if self.isScramble(s1[:i], s2[:i]) and self.isScramble(s1[i:], s2[i:]):
                return True
            if self.isScramble(s1[:i], s2[length - i:]) and self.isScramble(s1[i:], s2[:length - i]):
                return True
        return False

95 Unique Binary Search Trees II

'''
Example:
Input: 3
Output:
[
  [1,null,3,2],
  [3,2,null,1],
  [3,1,null,null,2],
  [2,1,3],
  [1,null,2,null,3]
]
Explanation:
The above output corresponds to the 5 unique BST's shown below:

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3
'''
class Solution:
    def generateTrees(self, n: int) -> List[TreeNode]:
        if n == 0:
            return []
        return self.dfs(1, n)
    
    def dfs(self, left, right):
        if left > right:
            return [None]
        res = []
        for i in range(left, right + 1):
            leftNode = self.dfs(left, i-1)
            rightNode = self.dfs(i+1, right)
            for l_n in leftNode:
                for r_n in rightNode:
                    root = TreeNode(i)
                    root.left = l_n
                    root.right = r_n
                    res.append(root)

        return res

130 Surrounded Regions

'''
X X X X
X O O X
X X O X
X O X X
After running your function, the board should be:
X X X X
X X X X
X X X X
X O X X
'''
class Solution:
    # dfs
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        def dfs(x, y):
            if x < 0 or x >= m or y < 0 or y >=n or board[x][y] != 'O': return
            board[x][y] = 'D'
            dfs(x-1, y)
            dfs(x+1, y)
            dfs(x, y-1)
            dfs(x, y+1)
            
        m = len(board)
        if m == 0: return
        n = len(board[0])
        for i in range(m):
            dfs(i, 0)
            dfs(i, n-1)
        for j in range(n):
            dfs(0, j)
            dfs(m-1, j)
        for i in range(m):
            for j in range(n):
                if board[i][j] == 'O':
                    board[i][j] = 'X'
                elif board[i][j] == 'D':
                    board[i][j] = 'O'

200 Number of Islands

# # method1 floodfill
# class Solution:
    
#     def numIslands(self, grid: List[List[str]]) -> int:
#         if not grid or not grid[0]:
#             return 0
        
#         self.dx = [-1, 1, 0, 0]
#         self.dy = [0, 0, -1, 1]
#         self.max_x = len(grid)
#         self.max_y = len(grid[0])
        
#         self.grid = grid
#         self.visited = set()
#         res = 0
#         for i in range(self.max_x):
#             for j in range(self.max_y):
#                 res += self.floodfill_dfs(i, j)
#         return res
    
#     def floodfill_dfs(self, x, y):
#         if not self._is_valid(x, y):
#             return 0
#         self.visited.add((x, y))
#         for k in range(4):
#             self.floodfill_dfs(x+self.dx[k], y+self.dy[k])
#         return 1
        
#     def _is_valid(self, x, y):
#         if x < 0 or x >= self.max_x or y < 0 or y >= self.max_y:
#             return False
#         if (x, y) in self.visited or self.grid[x][y] == '0':
#             return False
#         return True

# method2 UnionFind

class UnionFind():
    def init(self, grid):
        m, n = len(grid), len(grid[0])
        self.count = 0
        self.parent = [-1] * (m*n)
        self.rank = [0] * (m*n)
        for i in range(i):
            for j in range(j):
                if grid[i][j] = '1':
                    self.parent[i*n + j] = i*n + j
                    self.count += 1
                    
    def find(self, i):
        if self.parent[i] != i:
            self.parent[i] = self.find(parent[i])
        return self.parent[i]
    
    def union(self, i, j):
        rooti = self.find(i)
        rootj = self.find(j)
        
        if rooti != rootj:
            if self.rank[rooti] > self.rank[rootj]:
                self.parent[rootj] = rooti
            elif self.rank[rooti] < self.rank[rootj]:
                self.parent[rooti] = rootj
            else:
                self.parent[rooti] = rootj
                self.rank[rootj] += 1
            self.count -= 1

            
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:     
        if not grid or not grid[0]:
            return 0
        uf = UnionFind(grid)
        directions = [(0,1),(0,-1),(1,0),(-1,0)]
        m, n = len(grid), len(grid[0])
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '0':
                    continue
                for d in directions:
                    nr, nc = i+d[0], j+d[1]
                    if nr >= 0 and nc >= 0 and nr < m and nc < n and grid[i][j] == '1':
                        uf.union(i*n+j, nr*n+nc)
        return uf.count

212 Word Search II

# 回溯法会超时
#class Solution:
#     def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        
#         self.res = []
#         num = len(words)
#         for i in range(num):
#             self.find(board, words[i])
#         return self.res
    
#     def find(self, board, word):
#         self.m = len(board)
#         self.n = len(board[0])
#         self.visited = set()
#         self.dir = [[0, 1], [0, -1], [1, 0], [-1, 0]]
#         for i in range(self.m):
#             for j in range(self.n):
#                 if board[i][j] == word[0]:
#                     tmp = word
#                     #self.dfs(board, i, j, word[1:], tmp)
#                     if self.dfs(board, i, j, word[1:], tmp):
#                         #print('res append word')
#                         if word not in self.res:
#                             self.res.append(word)
                    
#     def dfs(self, board, i, j, word, tmp):
#         if not word:
#             #print ('word length == 0')
#             #self.res.append(tmp)
#             return True
#         self.visited.add((i, j))
#         for d in self.dir:
#             #print (self.visited)
#             ni = i + d[0]
#             nj = j + d[1]
#             if not self.vaild(ni, nj) or board[ni][nj] != word[0]:
#                 continue
#             if self.dfs(board, ni, nj, word[1:], tmp):
#                 return True
#         self.visited.remove((i, j))
#         return False
        
            
#     def vaild(self, ni, nj):
#         if ni < 0 or nj < 0 or ni >= self.m or nj >= self.n or (ni, nj) in self.visited:
#             return False
#         return True
        
# 需要优化回溯算法以通过更大数据量的测试， 使用前缀树
class TrieNode:
    def __init__(self):
        self.children = {}
        self.Word = ''
        
class Solution:        
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        m = len(board)
        if m == 0:
            return []
        n = len(board[0])
        trie = self.buildTrie(words)
        self.res = []
        for i in range(m):
            for j in range(n):
                self.DFS(board, i, j, trie)
        return self.res
    
    def DFS(self, board, i, j, trie):
        if trie.Word:
            self.res.append(trie.Word)
            trie.Word = ''
        if i<0 or i>=len(board) or j<0 or j>=len(board[0]) or not board[i][j] in trie.children:
            return
        tmp,board[i][j]=board[i][j],'X'
        for dx,dy in zip((-1,0,1,0),(0,-1,0,1)):
            self.DFS(board,i+dx,j+dy,trie.children[tmp])
        board[i][j]=tmp

        
    def buildTrie(self, words):
        trie = TrieNode()
        for word in words:
            cur = trie
            for c in word:
                if c not in cur.children: cur.children[c] = TrieNode()
                cur = cur.children[c]
            cur.Word = word
        return trie

403 Frog Jump

'''
[0,1,3,5,6,8,12,17]

There are a total of 8 stones.
The first stone at the 0th unit, second stone at the 1st unit,
third stone at the 3rd unit, and so on...
The last stone at the 17th unit.

Return true. The frog can jump to the last stone by jumping 
1 unit to the 2nd stone, then 2 units to the 3rd stone, then 
2 units to the 4th stone, then 3 units to the 6th stone, 
4 units to the 7th stone, and 5 units to the 8th stone.
'''
class Solution:
    def canCross(self, nums):
        """
        :type stones: List[int]
        :rtype: bool
        """
        stone={num:1 for num in nums}
        index=1
        k=1
        self.res={}
        return self.jump(stone,1,1,nums[-1])
    
    def jump(self,stone,index,k,n):
        if index==n:
            return True
        if index>n or (index not in stone) :
            return False
        if (index,k) in self.res:
            return self.res[(index,k)]
        if k==1:
            judge=self.jump(stone,index+k,k,n) or self.jump(stone,index+k+1,k+1,n)
            self.res[(index,k)]=judge
            return judge
        if k>1:
            judge= self.jump(stone,index+k,k,n) or self.jump(stone,index+k+1,k+1,n) or self.jump(stone,index+k-1,k-1,n)
            self.res[(index,k)]=judge
            return judge        

437 Path Sum III

'''
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1

Return 3. The paths that sum to 8 are:
1.  5 -> 3
2.  5 -> 2 -> 1
3. -3 -> 11
'''
class Solution:
    def pathSum(self, root: TreeNode, sum: int) -> int:
        if root is None:
            return 0
        res = self.findpath(root, sum)
        res += self.pathSum(root.left, sum)
        res += self.pathSum(root.right, sum)
        return res
        
    def findpath(self, node, num):
        if node is None:
            return 0
        res = 0
        if node.val == num:
            res += 1
        res += self.findpath(node.left, num-node.val)
        res += self.findpath(node.right, num-node.val)
        return res

980 Unique Paths III

'''
On a 2-dimensional grid, there are 4 types of squares:
1 represents the starting square.  There is exactly one starting square.
2 represents the ending square.  There is exactly one ending square.
0 represents empty squares we can walk over.
-1 represents obstacles that we cannot walk over.

Input: [[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
Output: 2
Explanation: We have the following two paths: 
1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2)
2. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2)
'''
class Solution:
    def uniquePathsIII(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        
        zeronum = 0
        
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 0:
                    zeronum += 1
                    
        self.res = 0
        self.dir = [[0, 1], [0, -1], [-1, 0], [1, 0]]
        self.visited = set()
        #print(self.visited)
            
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    self.dfs(grid, i, j, zeronum, 0)
        return self.res
    
    def dfs(self, grid, i, j, zeronum, cnt):
        if grid[i][j] == 2 and cnt == zeronum:
            self.res += 1
        if (grid[i][j] == 0 or grid[i][j] == 1):
            self.visited.add((i, j))
            print(self.visited)
            for d in self.dir:
                nx = i + d[0]
                ny = j + d[1]
                if nx < 0 or ny < 0 or nx >= len(grid) or ny >= len(grid[0]) or grid[nx][ny] == -1 or (nx, ny) in self.visited:
                    continue
                if grid[i][j] == 0:
                    self.dfs(grid, nx, ny, zeronum, cnt+1)
                if grid[i][j] == 1:
                    self.dfs(grid, nx, ny, zeronum, cnt)
            self.visited.remove((i, j))