LeetCode-DFS

LeetCode22. 括号生成

class Solution(object):
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        res = []
        cur = ""
        self.dfs(res,cur,n,0,0)
        return res
    def dfs(self,res,cur,n,l,r):
        if l==n:
            res.append(cur+')'*(n-r))
            return 
        self.dfs(res,cur+'(',n,l+1,r)
        if r<l:
            self.dfs(res,cur+')',n,l,r+1)

LeetCode37 解数独

编写一个程序，通过已填充的空格来解决数独问题。
一个数独的解法需遵循如下规则：

1. 数字 1-9 在每一行只能出现一次。
2. 数字 1-9 在每一列只能出现一次。
3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
   Note:

• 给定的数独序列只包含数字 1-9 和字符 ‘.’ 。
• 你可以假设给定的数独只有唯一解。
• 给定数独永远是 9x9 形式的。

class Solution(object):
    def solveSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: void Do not return anything, modify board in-place instead.
        """
        self.sudoku_core(board)
        return
    def sudoku_core(self,board):
        for i in range(9):
            for j in range(9):
                if board[i][j] == '.':
                    for k in range(1,10):
                        if self.is_value_sudoku(board,i,j,k):
                            board[i][j] = str(k)
                            if self.sudoku_core(board):
                                return True
                            board[i][j] = '.'
                    return False
        return True
        
    def is_value_sudoku(self,board,i,j,k):
        for l in board[i]:
            if l == str(k):
                return False
        for l in range(9):
            if board[l][j] == str(k):
                return False
        for m in range(int(i/3)*3,int(i/3)*3+3):
            for n in range(int(j/3)*3,int(j/3)*3+3):
                if board[m][n] == str(k):
                    return False
        return True

LeetCode51. N皇后

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

class Solution(object):
    def solveNQueens(self, n):
        """
        :type n: int
        :rtype: List[List[str]]
        """
        pos = [-1]*n
        res = []
        row = 0
        self.n_queens_core(res,pos,row,n)
        return res
    def n_queens_core(self,res,pos,row,n):
        if row == n:
            st = [['.']*n for i in range(n)]
            for i in range(n):
                st[i][pos[i]] = 'Q'
            st = [''.join(i) for i in st]
            res.append(st)
        else:
            for col in range(n):
                if self.is_value(pos,row,col):
                    pos[row] = col
                    self.n_queens_core(res,pos,row+1,n)
                    pos[row] = -1
    def is_value(self,pos,row,col):
        for i in range(row):
            if col==pos[i] or abs(row-i) == abs(pos[i]-col):
                return False
        return True

LeetCode51. N皇后2

class Solution(object):
    def totalNQueens(self, n):
        """
        :type n: int
        :rtype: int
        """
        pos = [-1]*n
        res,row = [0],0
        self.n_queens_core(res,pos,row,n)
        
        return res[0]
    def n_queens_core(self,res,pos,row,n):
        if row==n:
            res[0] += 1
        else:
            for col in range(n):
                if self.is_value(pos,row,col):
                    pos[row] = col
                    self.n_queens_core(res,pos,row+1,n)
                    pos[row] = -1
                    
    def is_value(self,pos,row,col):
        for i in range(row):
            if col == pos[i] or abs(i-row) == abs(col-pos[i]):
                return False
        return True

LeetCode79. 单词搜索

给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

class Solution:
    def exist(self, board, word):
        """
        :type board: List[List[str]]
        :type word: str
        :rtype: bool
        """
        m = len(board)
        if m == 0:
            if word:
                return False
            else:
                return True
        n = len(board[0])
        has_visit = [[False]*n for i in range(m)]
        for i in range(m):
            for j in range(n):
                if self.search(board,word,i,j,has_visit,0,m,n):
                    return True
        return False
    
    def search(self,board,word,i,j,has_visit,k,m,n):
        if k == len(word):
            return True
        is_word = False
        if 0<=i<m and 0<=j<n and not has_visit[i][j] and board[i][j] == word[k]:
            has_visit[i][j] = True
            is_word = self.search(board,word,i+1,j,has_visit,k+1,m,n) or self.search(board,word,i-1,j,has_visit,k+1,m,n) \
            or self.search(board,word,i,j+1,has_visit,k+1,m,n) or self.search(board,word,i,j-1,has_visit,k+1,m,n)
            has_visit[i][j] = False
        return is_word

LeetCode131. 分割回文串

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
返回 s 所有可能的分割方案。

class Solution(object):
    def partition(self, s):
        """
        :type s: str
        :rtype: List[List[str]]
        """
        n = len(s)
        res = []
        self.dfs(s,[],0,res,n)
        return res
        
    def is_palindrome(self,s,start,end):
        while start < end:
            if s[start] != s[end]: return False
            start +=1
            end -= 1
        return True
    def dfs(self,s,cur,start,res,n):
        if start == n:
            res.append(cur)
        for i in range(start,n):
            if self.is_palindrome(s,start,i):
                self.dfs(s,cur+[s[start:i+1]],i+1,res,n)