DFS专题

所谓深度优先搜索（Depth First Search）是从某个节点一直往下搜索，直到没有可以搜索的点则返回。DFS适用于找到所有的方案的题，排列或者组合。

组合（Combination）

leetcode078 subSets

找到数组的所有子集，这里使用DFS（递归实现（Recursion））。

class Solution:
    """
    @param nums: A set of numbers
    @return: A list of lists
    """
    def subsets(self, nums):
        # 从空集开始搜索，每次将nums的节点加入空集中
        result = []
        tmp = []
        
        if nums is None:
            return None
        
        nums.sort()
        
        startIndex = 0
        self.dfsHelper(nums, startIndex, tmp, result)
        
        return result
        
    def dfsHelper(self, nums, startIndex, tmp, result):
        # 递归出口
        tmp_copy = tmp.copy()
        result.append(tmp_copy)
        
        if startIndex == len(nums):
            return
        
        for i in range(startIndex, len(nums)):
            tmp.append(nums[i])
            self.dfsHelper(nums, i + 1, tmp, result)
            tmp.pop()
        return

CombinationSum系列

给定数组和目标数，求数组中和为target的组合

leetcode039 CombinationSum

数组中的每一个数可以使用多次.

class Solution:
    """
    @param candidates: A list of integers
    @param target: An integer
    @return: A list of lists of integers
    """
    def combinationSum(self, candidates, target):
        if candidates is None:
            return None
        
        # candidates去重
        candidates = self.deDuplicate(candidates)
        
        result = []
        tmp = []
        startIndex = 0
        
        self.dfsHelper(candidates, target, startIndex, tmp, result)
        
        return result
    
    def dfsHelper(self, candidates, target, startIndex, tmp, result):
        # 递归的出口
        if  target == 0:
            result.append(tmp.copy())
            tmp = []
            return
        
        # 递归
        for i in range(startIndex, len(candidates)):
            if candidates[i] > target:
                return
            self.dfsHelper(candidates, target - candidates[i], i, tmp + [candidates[i]], result)
            
        return
    
    def deDuplicate(self, nums):
        nums = list(set(nums))
        nums.sort()
        return nums

leetcode040 CombinationSumII

每个答案中同一个数只能使用一次

class Solution:
    """
    @param candidates: A list of integers
    @param target: An integer
    @return: A list of lists of integers
    """
    def combinationSum2(self, candidates, target):
        if candidates is None:
            return None
        
        # candidates排序
        candidates.sort()
        
        result = []
        tmp = []
        startIndex = 0
        
        self.dfsHelper(candidates, target, startIndex, tmp, result)
        
        return result
    
    def dfsHelper(self, candidates, target, startIndex, tmp, result):
        # 递归的出口
        if  target == 0:
            result.append(tmp.copy())
            tmp = []
            return
        
        # 递归
        for i in range(startIndex, len(candidates)):
            # 去重, 第一个大循环中依次进数时，判断第二个数进入的数和第一个数不同
            if (i != startIndex) and (candidates[i] == candidates[i - 1]):
                continue
            if candidates[i] > target:
                return
            self.dfsHelper(candidates, target - candidates[i], i + 1, tmp + [candidates[i]], result)
            
        return

leetcode1278 PalindromePartition

回文串划分（划分某个字符串为回文子串，输出所有答案）

class Solution:
    """
    @param: s: A string
    @return: A list of lists of string
    """
    def partition(self, s):
        if s is None:
            return None
        
        tmp = []
        result = []
        startIndex = 0
        
        self.dfsHelper(s, startIndex, tmp, result)
        
        return result
    
    def dfsHelper(self, s, startIndex, tmp, result):
        if startIndex == len(s):
            result.append(tmp.copy())
            return
        
        
        for i in range(startIndex, len(s)):
            substr = s[startIndex:i+1]
            if not self.isPalindrome(substr):
                continue
            tmp.append(substr)
            self.dfsHelper(s, i+1, tmp, result)
            tmp.pop()
            
        return
    
    def isPalindrome(self, s):
        return s == s[::-1]

排列（Permutation）

leetcode046 permutations

给定数组，求数组中数的所有排列

class Solution:
    """
    @param: nums: A list of integers.
    @return: A list of permutations.
    """
    def permute(self, nums):
        if nums is None:
            return None
            
        result = []
        tmp = []
        
        self.dfsHelper(nums, tmp, result)
        
        return result
    
    def dfsHelper(self, nums, tmp, result):
        if len(nums) == 0:
            result.append(tmp.copy())
            return
        
        # 递归
        for i in range(len(nums)):
            tmp.append(nums[i])
			# 这里python进行数组的拼接，形成不同的搜索起点
            self.dfsHelper(nums[:i] + nums[i+1:], tmp, result)
            tmp.pop()
        
        return

leetcode047 permutationsII

给定带有重复元素的数组，求所有不同的排列（去重问题）

class Solution:
    """
    @param: :  A list of integers
    @return: A list of unique permutations
    """

    def permuteUnique(self, nums):
        if nums is None:
            return None
            
        result = []
        tmp = []
        
        nums.sort()
        
        self.dfsHelper(nums, tmp, result)
        
        return result
    
    def dfsHelper(self, nums, tmp, result):
        if len(nums) == 0:
            result.append(tmp.copy())
            return
        
        # 递归
        for i in range(len(nums)):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            tmp.append(nums[i])
            self.dfsHelper(nums[:i] + nums[i+1:], tmp, result)
            tmp.pop()
        
        return

图中的搜索

wordLadder

单词阶梯(给出两个单词start，end和一个字典，找出start变换到end的最短序列，每次变换只改变一个字母)

• leetcode127 wordLadder
  只需要求出路径的长度, BFS即可。原题里面给的wordList很长，这时使用remove的方法比较快。

class Solution:
    """
    @param: start: a string
    @param: end: a string
    @param: dict: a set of string
    @return: An integer
    """
    def ladderLength(self, start, end, wordList):
            
        def bfs(start, end, wordList):
            
            wordList = set(wordList)
                
            q = collections.deque()
            q.append((start, 1))
            
            while q:
                word, step = q.popleft()
                if word == end:
                    return step

                for i in range(len(word)):
                    for temp_char in 'abcdefghijklmnopqrstuvwxyz':
                        neighbor = word[:i] + temp_char + word[i+1:]
                        if neighbor in wordList:
                            q.append((neighbor, step + 1))
                            wordList.remove(neighbor)
                        
            return 0
        
        return bfs(start, end, wordList)

• leetcode126 wordLadderII
  找出所有的最短变换序列，这里给的case不是很强。考察一次bfs建图，和dfs寻找路径。

class Solution:
    """
    @param: start: a string
    @param: end: a string
    @param: dict: a set of string
    @return: a list of lists of string
    """
    def findLadders(self, start, end, wordList):
		if end not in wordList:
			return []

        wordList.append(start)
        
        d = self.construct_dict(wordList)
        
        # bfs构建start到每个单词的距离
        distance = {}
        self.bfsHelper(start, end, wordList, distance, d)
        
        # dfs搜索所有的答案
        result = []
        tmp = []
        tmp.append(start)
        self.dfsHelper(start, end, distance, d, tmp, result)
        
        return result
      
    def construct_dict(self, wordList):
        d = {}
        for word in wordList:
            for i in range(len(word)):
                s = word[:i] + '_' + word[i+1:]
                d[s] = d.get(s, []) + [word]
        return d
    
    def get_next_words(self, word, d):
        next_words = []
        for i in range(len(word)):
            s = word[:i] + '_' + word[i+1:]
            for next_word in d.get(s, []):
                if next_word not in next_words:
                    next_words.append(next_word)
        return next_words
        
    def bfsHelper(self, start, end, wordList, distance, d):
        q = collections.deque()
        q.append(start)
        
        distance[start] = 0
        while q:
            word = q.popleft()
            for next_word in self.get_next_words(word, d):
                if next_word not in distance:
                    distance[next_word] = distance[word] + 1
                    q.append(next_word)
        return
    
    def dfsHelper(self,cur_word, end, distance, d, tmp, result):
        # 出口
        if cur_word == end:
            result.append(tmp.copy())
            return
        # 递归
        for next_word in self.get_next_words(cur_word, d):
            # print(next_word)
            if distance[next_word] != distance[cur_word] + 1:
                continue
            tmp.append(next_word)
            # print(tmp)
            self.dfsHelper(next_word, end, distance, d, tmp, result)
            tmp.pop()
        return

矩阵中的搜索

leetcode200 NumberOfIsland

老题，矩阵中1表示陆地，0表示水域。求岛屿的数量，连在一起的陆地可以看做一个岛屿，上下左右都不连通视为两个岛屿。可以用BFS做，这里使用DFS。

class Solution:
    """
    @param grid: a boolean 2D matrix
    @return: an integer
    """
    def numIslands(self, grid):
        count = 0
        n = len(grid)
        if not n:
            return count
        
        m = len(grid[0])
        if not m:
            return count
            
        for i in range(n):
            for j in range(m):
                if grid[i][j] == "1":
                    # print("yes")
                    count += 1
                    # 将此位置的所有连通块置为0
                    self.dfsHelper(grid,i,j)
                    
        return count
        
    def dfsHelper(self, grid, x, y):
        # dfs的出口
        if not self.isValid(grid, x, y):
            return

        # 当前位置设为0, 下次遍历到此直接返回
        grid[x][y] = "0"

        deltaX = [1, 0, -1, 0]
        deltaY = [0, 1, 0, -1]

        for i in range(4):
            newX = x + deltaX[i]
            newY = y + deltaY[i]
            self.dfsHelper(grid, newX, newY)

        return
    
    def isValid(self, grid, x, y):
        n = len(grid)
        m = len(grid[0])
        if (x < n) and (x >= 0) and (y < m) and (y >= 0) and grid[x][y] == "1":
            return True
        else:
            return False