[数据结构与算法]深度优先搜索算法（DFS）

BFS

• java：用hashmap/hashset来去重
• python:dict/set来去重

分治法 divide & conquer

• 将大规模问题拆分为若干个小规模同类型问题去处理
• 再把子问题分为更小的问题，直到最后子问题可以简单求解
• 最后将子问题的解合并就是原问题的解
  ?通常用递归方法来解决

搜索

?宽度优先搜索
?深度优先搜索(DFS) = 回溯
?遍历法：可用递归或迭代（非递归）
?分治法：可用递归或迭代（非递归）
注：递归和非递归是算法的一种实现方式而不是算法

递归三要素：
1.递归的定义
2.递归的拆解
3.递归的出口

Binary search tree要点
定义：左子树节点的值<根节点的值，右子树节点的值>=根节点的值
中序遍历：对二叉查找树使用中序遍历，则会发现中序遍历的list列表是有序的（不下降的顺序，有些相邻点可能相等）
?若二叉树中序遍历不是“不下降”序列，则一定不是BST
?若二叉树的中序遍历是不下降，也未必是BST，如[1,1,1]

平衡二叉树（balanced binary tree）
?平衡二叉树可以是一棵空树
?左右子树高度差不大于1
?子树也必须是一棵平衡二叉树

二叉树的问题大部分可以用分治法的算法思想，DFS的算法和递归的程序设计方式去进行求解。
递归就是当多重for循环层数不确定时候，一个更优雅实现多重循环的方式。

import string
from collections import deque

"""
combination
"""

# ex1: letter combinations

class solution1():
    def __init__(self):
        self.KEYBOARD = {
            '2': 'abc',
            '3': 'def',
            '4': 'ghi',
            '5': 'jkl',
            '6': 'mno',
            '7': 'pqrs',
            '8': 'tuv',
            '9': 'wxyz'}

    def letterCombination(self, digits):
        if not digits:
            return []
        combinations = []
        self.dfs(digits, 0, [], combinations)
        return combinations

    # 递归三要素之一：递归的定义
    # digits表示输入的数字
    # index表示dfs要处理digits[index]所代表的的数字
    # combination表示到目前为止得到的组合
    # combinations代表目前为止找到的完整组合
    def dfs(self, digits, index, combination, combinations):
        # 递归三要素之三：递归出口
        if index == len(digits):
            combinations.append(''.join(combination))
            return

        # 递归三要素之二：递归的拆解
        # 遍历index位置的数字可表示的字母加入combo
        for letter in self.KEYBOARD[digits[index]]:
            combination.append(letter)
            self.dfs(digits, index + 1, combination, combinations)
            combination.pop()

# ex2: k sum II
class solution2():

    def kSumII(self, A, k, target):
        A.sort()
        subsets = []
        self.dfs(A, 0, k, target, [], subsets)
        return subsets

    # 递归三要素之一：递归的定义
    # 从A的index位置开始，选k个数字放入subset，满足k个数字和为target
    def dfs(self, A, index, k, target, subset, subsets):
        # 递归三要素之三：递归的出口
        # 若找到k个数字之和为target，记录答案，并返回
        if k == 0 and target == 0:
            subsets.append(list(subset))
            return
        # 同样是递归出口，若找不到结果
        #1.当0个数字之和依然没找到target，则返回
        #2.或者当数字和已经超出target，则返回
        # 本题保证所有的数都是正整数，若无该条件，则#2不能return
        if k == 0 or target <= 0:
            return

        # 递归三要素之二：递归的拆解
        for i in range(index, len(A)):
            # 把位置为i的数字加入
            subset.append(A[i])
            # 从A的第i+1位置开始，选k-1个数字加入subset
            # 满足k-1个数字和为target-A[i]
            self.dfs(A, index + 1, k - 1, target - A[i], subset, subsets)
            # 包括backtracking，把位置为i的数字移除
            subset.pop()

# ex3: combination sum
class solution3():
    def combinationSum(self, candidates, target):
        if not candidates:
            return []
        results = []
        unique_sorted_numbers = sorted(list(set(candidates)))
        self.dfs(unique_sorted_numbers, 0, [], target, results)
        return results

    # 递归三要素之一：递归的定义
    def dfs(self, nums, index, current_result, remain_target, results):
        #递归三要素之三：递归的出口
        if remain_target == 0:
            return results.append(list(current_result))

        # 递归三要素之二：递归的拆解，挑出一个数放入current
        for i in range(index, len(nums)):
            # 若剩余和比当前数字小，不考虑当前数字和之后的更大数字，可直接跳出当前的递归
            if remain_target < nums[i]:
                break
            # 把位置为i的数字加入
            current_result.append(nums[i])
            # 递归到下一层去选下一个数字
            # 这里传入i不是i+1，表示下一层可以重复使用当前的数字
            self.dfs(nums, i, current_result, remain_target - nums[i], results)
            # 把位置为i的数字移除
            current_result.pop()

# ex4: string permutation
class solution4():
    def stringPermutation(self, str):
        # 特殊情况处理，若str = '',返回['']
        if str is None:
            return
        # 排序所有字母，排序的意义：
        #1.可按字母序得到结果
        #2.相同字母在一起，方便去重
        chars = sorted(list(str))
        #记录哪些字母已经在permutation中被用过，初始值均为false
        visited = [False] * len(chars)
        #存放不同的permutation结果
        permutations = []
        self.dfs(chars, visited, [], permutations)
        return permutations

    # 递归三要素之一：递归的定义
    def dfs(self, chars, visited, permutation, permutations):
    # 递归三要素之三：递归的出口
    #若当前permutation长度 = 跟定字母的总个数
    #则说明所有字母已被用掉，找到了一个permutation
        if len(permutation) == len(chars):
            permutations.append(''.join(permutation))
            return

        # 递归三要素之二：递归的拆解
        for i in range(len(chars)):
            #同一个位置上的字母用过则不用再用
            if visited[i]:
                continue
            # 去重：不同位置的同样字符，必须按照从左到右顺序用
            # 即前面的相同字符先被用掉，才能用后面的相同字符，这也是为什么上面要先sort
            if i >0 and chars[i-1] == chars[i] and not visited[i-1]:
                continue

            # 设置位置为i的字符已被用掉
            visited[i] = True
            #把位置为i的字符加入
            permutation.append(chars[i])

            #找到所有以当前permutation开头的排列
            #递归到下一层去选permutation下一个字符
            self.dfs(chars, visited, permutation, permutations)

            #把位置为i的字母移除，回溯（backtracking）
            permutation.pop()
            # 由于该位置i的字母被移除，所以设置位置为i字母为未访问
            visited[i] = False

#ex5: word search II
DIRECTIONS = [(0,-1),(0,1),(-1,0),(1,0)]

class solution5():
    def wordSearchII(self, board, words):
        # 特殊情况处理
        if board is None or len(board) == 0:
            return []

        # word_set中含有所有需要寻找的词
        word_set = set(words)
        # prefix_set中含有所有词的前缀（包括整个词）
        prefix_set = set()

        for word in words:
            for i in range(len(word)):
                prefix_set.add(word[:i+1])

        result_set = set()

        # 遍历格子中每个点，从这个点开始，进行dfs
        for i in range(len(board)):
            for j in range(len(board[0])):
                self.search(
                    board,
                    i,
                    j,
                    board[i][j],
                    word_set,
                    prefix_set,
                    set([(i,j)]),
                    result_set,
                )

        return list(result_set)

    # word用于记录当前dfs路径中找到的词
    # visited用于标记在当前路径中走过的点
    def search(self, board, x, y, word, word_set, prefix_set, visited, result_set):
        # 如果不是prefix，没有必要继续走下去，回退一步
        if word not in prefix_set:
            return

        # 若找到一个词，记录下来，继续走
        # 为什么找到一个词还要往下走？
        # 因为可能还有一个词，包含了当前词作为前缀
        if word in word_set:
            result_set.add(word)

        for delta_x, delta_y in DIRECTIONS:
            x_ = x + delta_x
            y_ = y + delta_y

            # 若越界，或当前词被访问过，则跳过
            if not self.inside(board, x_, y_) or (x_, y_) in visited:
                continue
            # 标记这个词在当前路径被访问过，跳过
            visited.add((x_,y_))
            # 递归进行dfs，继续延伸路径
            self.search(
                board,
                x_,
                y_,
                word + board[x_][y_],
                word_set,
                prefix_set,
                visited,
                result_set
            )
            # 回溯：标记这点再当前路径中没有被访问过
            # dfs常见错误：没有清空之前的dfs数据
            visited.remove((x_,y_))

    # 判断是否越界
    def inside(self, board, x, y):
        return 0<=x<len(board) and 0<=y<len(board[0])

# ex6: word ladder ii
'''
start = 'hit'
end = 'zog'
dict = ['hot','dot','dog','lot','log']
'''
class solution6():
    def findLadders(self, start, end, d):
        d.add(start)
        d.add(end)

        distance = {}

        fromToDict = {}

        for s in d:
            fromToDict[s] = []
        self.bfs(start, fromToDict, distance, d)

        results = []
        self.dfs(start, end, distance, d, [], results, fromToDict, distance[end])

        return results

    def bfs(self, start, fromToDict, distance, d):
        distance[start] = 0
        queue = deque([start])
        while queue:
            curr_word = queue.popleft()
            for next_word in self.get_next_words(curr_word, d):
                if (next_word not in distance or distance[next_word] == distance[curr_word] + 1):
                    fromToDict[curr_word].append(next_word)

                if next_word not in distance:
                    distance[next_word] = distance[curr_word] + 1
                    queue.append(next_word)

    def dfs(self, curr_word, target, distance, d, path, results, fromToDict, min_len):
        if len(path) == min_len + 1:
            return

        path.append(curr_word)

        if curr_word == target:
            results.append(list(path))
        else:
            for nextWord in fromToDict[curr_word]:
                self.dfs(nextWord, target, distance, d, path, results, fromToDict, min_len)

        path.pop()

    def get_next_words(self, word, d):
        words = []
        for i in range(len(word)):
            for c in string.ascii_lowercase:
                if (word[i] == c):
                    continue
                next_word = word[:i] + c +word[i+1:]
                if next_word in d:
                    words.append(next_word)
        return words


if __name__ == '__main__':
    test = solution1()
    com = test.letterCombination(['2','3'])

    A = [1,3,4,6]
    test = solution2()
    sub = test.kSumII(A, 3, 8)

    candidates = [2,3,7]
    test = solution3()
    res = test.combinationSum(candidates, 7)

    chars ='abb'
    test = solution4()
    per = test.stringPermutation(chars)

    board = ['doaf','agai','dcan']
    words = ['dog','dad','dgdg','can','again']
    DIRECTIONS = [(0, -1), (0, 1), (-1, 0), (1, 0)]
    test = solution5()
    res = test.wordSearchII(board, words)

    start = 'hit'
    end = 'zog'
    dict = set(['hot', 'dot', 'dog', 'lot', 'log'])
    test = solution6()
    res = test.findLadders(start, end, dict)
    print(res)