中等难度-回溯算法

来源于leetcode题库17,22,39,78,79

17.电话号码的字母组合

题目描述
- 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
  给出数字到字母的映射与电话按键相同。注意 1 不对应任何字母。
示例

输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

题解

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []
        phone = {
            '2':['a','b','c'],
            '3':['d','e','f'],
            '4':['g','h','i'],
            '5':['j','k','l'],
            '6':['m','n','o'],
            '7':['p','q','r','s'],
            '8':['t','u','v'],
            '9':['w','x','y','z']
        }
        '''
        定义函数backtrack
        当nextdigit不为空，对于nextdigit[0]对应的每个字母letter
        执行回溯backtrack(conbination+letter,nextdigit[1:])
        直到nextdigit为空，最后将conbination加入到结果中
        '''
        def backtrack(conbination,nextdigit):
            if len(nextdigit) == 0:
                res.append(conbination)
            else:
                for letter in phone[nextdigit[0]]:
                    backtrack(conbination+letter,nextdigit[1:])
        res = []# 存放结果
        backtrack('',digits)
        return res

22.括号生成

题目描述
- 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。

示例

输入：n = 3
输出：[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]

题解

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        ''' 
        使用dfs构建树
        (1)左右括号的数量都大于0个才可以产生分支
        (2)产生左分支的时候，只看当前是否还有左括号可用即可
        (3)产生右分支的时候，受到左分支的限制，右边剩余可用括号数量
        严格大于左边可用括号数量才可以产生分支
        (4)左边和右边的剩余括号数量都等于0的时候结算
        '''
        res = []
        cur_str = ''
        def dfs(cur_str,left,right,n):
            '''
            cur_str:从根节点到叶子节点到路径字符串
            left:左括号已经使用的个数
            right:右括号已经使用的个数
            '''
            if left == n and right == n:
                res.append(cur_str)
                return
            if left < right:
                return
            if left < n:
                dfs(cur_str+'(',left+1,right,n)
            if right < n:
                dfs(cur_str+')',left,right+1,n)
        dfs(cur_str,0,0,n)
        return res

39.组合总和

题目描述
- 给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
  candidates 中的数字可以无限制重复被选取。
示例

示例 1：
输入：candidates = [2,3,6,7], target = 7,
所求解集为：
[
[7],
[2,2,3]
]
示例 2：
输入：candidates = [2,3,5], target = 8,
所求解集为：
[
[2,2,2,2],
[2,3,3],
[3,5]
]

题解
- 题解来自题解区大佬吴彦祖

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        if(not candidates):
            return []
        n=len(candidates)
        res=[]
        candidates.sort()
        def helper(i,tmp,target):
            if(target==0):
                res.append(tmp)
                return
            if(i==n or target<candidates[i]):
                return
            helper(i,tmp+[candidates[i]],target-candidates[i])
            helper(i+1,tmp,target)
        helper(0,[],target)
        return res

78.子集

题目描述
- 给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
  说明：解集不能包含重复的子集。
示例

输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

题解
- 来自题解区大佬powcai

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []
        n = len(nums)
        
        def helper(i, tmp):
            res.append(tmp)
            for j in range(i, n):
                helper(j + 1,tmp + [nums[j]] )
        helper(0, [])
        return res

79.单词搜索

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

board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
给定 word = "ABCCED", 返回 true
给定 word = "SEE", 返回 true
给定 word = "ABCB", 返回 false

题解

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        # 使用深度优先搜索
        if not board:   # 边界条件
            return False
        for i in range(len(board)):# 行
            for j in range(len(board[0])): # 列
                if self.dfs(board, i, j, word):
                    return True
        return False

    def dfs(self, board, i, j, word):
        if len(word) == 0: # 如果单词已经检查完毕
            return True
        # 如果路径出界或者矩阵中的值不是word的首字母，返回False
        if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]) or word[0] != board[i][j]:  
            return False
        tmp = board[i][j]  # 如果找到了第一个字母，检查剩余的部分
        board[i][j] = '0' # 当前位置赋值为0避免重复搜索
        # 上下左右四个方向搜索
        res = self.dfs(board,i+1,j,word[1:]) or self.dfs(board,i-1,j,word[1:]) or self.dfs(board,i,j+1,word[1:]) or self.dfs(board, i, j-1, word[1:]) 
        # 对四个方向搜索结束后将标记的点恢复原状
        board[i][j] = tmp  # 标记过的点恢复原状，以便进行下一次搜索
        return res