本文目录

  1. 电话号码的字母组合
  2. 括号生成
  3. 全排列
  4. 子集
  5. 单词搜索

电话号码的字母组合

题目描述

给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。

示例:

1
2
输入:digits = "23"
输出:["ad","ae","af","bd","be","bf","cd","ce","cf"]

提示:

  • 0 <= digits.length <= 4
  • digits[i] 是范围 [‘2’, ‘9’] 的一个数字。

题解

迭代法

我们需要列举出所有可能的字母组合,因此我们维护一个队里保存所有可能的字符串组合,然后遍历输入的数字,然后每次将对应的所有可能的字母加到当前的字符串后面,然后将所有的可能的字符串添加到队列中,直到遍历完所有数字。
python代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
dic = {'2':'abc', '3':'def', '4':'ghi','5':'jkl','6':'mno','7':'pqrs','8':'tuv','9':'wxyz'}
q = [] # 维护组合队列
for d in digits:
cur = dic[d] # 当前可能的输入字母
size = len(q) # 当前队列中组合的个数
cur_len = len(cur) # 当前可能输入的字母的个数
if size==0: # 如果队列为空,也就是一开始的时候
for j in range(cur_len): # 就将所有可能的字母加入队列
q.append(cur[j])
else: # 如果队列不为空
for i in range(size): # 遍历目前队列中所有的size个组合
top = q.pop(0) # 取出第一个组合
for j in range(cur_len): # 将此次所有可能的输入字符加到后面,然后加到队列中
q.append(top+cur[j])
return q # 遍历结束之后,所有的组合都保存在队列q中

回溯法

回溯法就是要枚举所有可能的答案。
回溯算法的模板如下:

1
2
3
4
5
6
7
8
9
10
11
def backtrack(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (本层的所有元素) {
        处理元素;
        backtrack(下一层); // 递归
        回退,撤销处理结果
    }

在本题中的具体代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
dic = {'2':'abc', '3':'def', '4':'ghi','5':'jkl','6':'mno','7':'pqrs','8':'tuv','9':'wxyz'}
q = [] # 保存所有组合
cur = "" # 维护一个到当前未知的字符组合
if len(digits)==0:
return q

# index 表示目前访问到的数字的下标,cur为到index前一个为止的字符组合
def backtrack(index, cur):
if index == len(digits): # 终止条件:digits中的所有元素都被访问了
q.append(cur) # 则形成一个可行答案
else:
toadd = dic[digits[index]] # 此次可能输入的字符
for i in range(len(toadd)): # 依次处理每个可能输入的字符
cur = cur + toadd[i] # 把当前字符加上
backtrack(index+1, cur) # 继续搜索下一个
cur = cur[:-1] # 回退,去掉最后加上的字符

backtrack(0, cur)
return q

括号生成

题目描述

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

示例:

1
2
3
4
5
6
7
示例 1:
输入:n = 3
输出:["((()))","(()())","(())()","()(())","()()()"]

示例 2:
输入:n = 1
输出:["()"]

提示:

  • 1 <= n <= 8

题解

回溯法

利用回溯法穷举所有的可能,如果是有效的括号组合则保存下来。
因此需要设计一个函数is_valid(str)来判断所生成的字符串是否是有效的括号组合,这可以利用栈来实现。
具体python代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
res = [] # 保存结果

# 判断给定的字符串ans是否是有效的括号组合
def is_valid(ans):
stk = []
for c in ans:
if c=='(':
stk.append(c)
elif c==')':
if len(stk)==0:
return False
top = stk.pop(-1)
if top==')':
return False
if len(stk)==0:
return True
else:
return False

# 回溯算法,index是当前访问的字符串的下标数,cur保存到目前为止生成的字符串
def backtrack(index, cur):
if index == n*2: # 注意因为一个括号有两个字符,因此长度为n*2
if is_valid(cur): # 如果是有效的括号组合,则添加到结果中
res.append(cur)
else: # 下面分别处理这一层的元素,一层有两个元素,分别为左括号'('和右括号')'
cur = cur + '(' # 尝试左括号
backtrack(index+1, cur)
cur = cur[:-1] # 回退

cur = cur + ')' # 尝试右括号
backtrack(index+1, cur)
cur = cur[:-1] # 回退

backtrack(0, "")
return res

不过该方法要穷举所有可能的括号组合,因此效率并不高。

回溯优化

实际上我们不需要枚举出所有的可能的括号组合方式,然后对每个进行判断是否有效。
一个有效的括号组合是有一定的规则的:

  1. 总共n个括号,有效的括号组合一定有n个左括号和n个右括号
  2. 每个右括号一定有一个左括号优先于它加入
  3. 在得到最终答案之前,左括号的数量一定比右括号的数量多

根据上面三个规则,我们可以直接判断当前字符串是否是一个有效的括号组合。
同时,在生成字符串的时候,优先生成左括号,然后再生成右括号进行匹配。
python代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
res = [] # 保存结果列表

def backtrack(left, right, cur): # left与right分别记录当前左括号和右括号的数量
if left + right == 2*n: # 如果左右括号之和为2n,说明这是一条有效的结果
res.append(cur)
return
if left < n: # 如果左括号小于n,就一直加入左括号
cur = cur + '('
backtrack(left+1, right, cur)
cur = cur[:-1]
if right < left: # 左括号会挨个弹出,然后尝试加入右括号,依次尝试每个可能的组合
cur = cur + ')'
backtrack(left, right+1, cur)
cur = cur[:-1]

backtrack(0, 0, "")
return res

全排列

题目描述

给定一个不含重复数字的数组 nums ,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例:

1
2
3
4
5
6
7
8
9
10
11
示例 1:
输入:nums = [1,2,3]
输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2:
输入:nums = [0,1]
输出:[[0,1],[1,0]]

示例 3:
输入:nums = [1]
输出:[[1]]

提示

  • 1 <= nums.length <= 6
  • -10 <= nums[i] <= 10
  • nums 中的所有整数 互不相同

题解

回溯法

求解全排列,可以看做是每次从原列表中选择一个数,有多少种不同的选择方案,而且是不放回选择。
使用回溯方法来解,使用一个index来记录当前要选择的是第几个数,当所有数都选择完毕(即index==len(nums))时,则得到一个答案,并将它记录下来。
每次选择数字的时候,因为是不放回抽取,因此需要排除掉已经选择的数字。
第index个位置有(len(nums)-index)个选择方案,因此需要尝试每个不同的方案。

python代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
res = [] # 维护答案列表

def backtrack(index, ans): # index表示目前在选第index个数,ans为目前已经选择了的数字列表
if index == len(nums): # 如果所有数都选择完毕
res.append([x for x in ans]) # 记录答案
return
for n in nums: # 第index个位置有(len(nums)-index)个选择方案
if n not in ans: # 排除了已经选择的数字
ans.append(n)
backtrack(index+1, ans)
ans.pop(-1)

backtrack(0, [])
return res

swap选择法

上面的方法在选择每一个数字时,还需要判断该数字是否已经被选过if n not in ans,当数字个数很多的时候,这种判断可能会非常耗时。
一种避免这种判断的方法:

因为第index个位置有(len(nums)-index)个选择,所以我们在循环的时候,保证一定的顺序访问,就可以只访问剩下的这些元素。
例如,我们将所有已经选择了的元素移动到index之前(因为我们选择了index-1个元素,所以这index-1个元素可以放到index位置之前),而index之后放剩余的没有被选择的元素。
这样,我们在每次选择一个元素时,只需要遍历[index, N-1]这些元素即可。

这就是使用swap来选择元素的一个好处。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
res = [] # 维护答案列表

def backtrack(index): # 填位置index的元素
if index == len(nums): # 如果所有位置都填完,则记录答案
res.append([x for x in nums])
return
for i in range(index, len(nums)): # 对于位置index,只遍历[index, len(nums)-1]的元素(这些是没有被选择过的)
nums[index], nums[i] = nums[i], nums[index] # 交换index与i的元素,这样相当于在位置index原则了第i个元素nums[i],同时将nums[i]移动到了index之前,表示该元素已经选择过了。原来index位置的元素移动到了index之后(位置i),表示该元素还没有选择过。
backtrack(index+1) # 接着递归填下一个元素
nums[index], nums[i] = nums[i], nums[index] # 回退

backtrack(0)
return res

子集

题目描述

给你一个整数数组 nums ,数组中的元素 互不相同 。返回该数组所有可能的子集(幂集)。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例:

1
2
3
4
5
6
7
示例 1:
输入:nums = [1,2,3]
输出:[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2:
输入:nums = [0]
输出:[[],[0]]

提示:

  • 1 <= nums.length <= 10
  • -10 <= nums[i] <= 10
  • nums 中的所有元素 互不相同

题解

回溯法

这道题乍一看和全排列有点像,但是仔细一想又有很多不一样的地方。
之前的回溯题,大多会使用一个index来指示目前访问到了哪一个位置,这时会发现,之前的答案元素个数大多都是固定的值,即给定固定个数个空位,去给每个空位填上对应的内容。
例如全排列,每个答案的元素个数就是所有数的个数N,即为N个空位填上相应的数字;
括号生成中答案的字符数都是2n,可以理解为为每个空位填上相应的括号(左括号or右括号);
电话号码的随机数组合中index也用来指示目前处理到的数字的位置,也是一个定值(数字个数N),而答案中字符个数也和数字个数相同,即给N个空位,填上相应的字符。

而这道题中,答案的元素个数却不一样,元素个数从0个到N个都有。于是就不知道从何下手了。

其实,这个题换种思考方式,会发现这道题也可以转换为这种“为固定长度的空位填答案”的模式。
例如示例中nums=[1,2,3],可以理解为,我们需要处理长度为3的空位,每个空位只能填0或1,0表示不选择当前位置的元素,1则表示选择当前位置的元素。
因此在这里,index仍然表示空位的位置,只是对每个空位来说,只有两种可能的选择(0 or 1)。

于是,python 回溯代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
res = [] # 维护答案列表
N = len(nums) # 空位个数,也就是元素个数

def backtrack(index, ans): # index指示空位下标,ans为当前答案
if index == N: # 如果所有空位都选择完毕(即每个位置0或1都已经确定,则确定了一个答案)
res.append([x for x in ans])
return

# 因为每个index位置有两种选择,下面分别处理两种选择
# 第一种,index位置为1,则选择nums[index]
ans.append(nums[index])
backtrack(index+1, ans)
ans.pop(-1)
# 第二中,index位置为0,则不添加任何元素,直接填下一个空
backtrack(index+1, ans)
backtrack(0, [])
return res

单词搜索

题目描述

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中,返回 true ;否则,返回 false 。

单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例

单词搜索_中级_回溯.jpg

1
2
输入:board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出:true

提示:

  • m == board.length
  • n = board[i].length
  • 1 <= m, n <= 6
  • 1 <= word.length <= 15
  • board 和 word 仅由大小写英文字母组成

进阶:你可以使用搜索剪枝的技术来优化解决方案,使其在 board 更大的情况下可以更快解决问题?

题解

回溯+DFS

给定一个长度为N的目标单词word,相当于我们需要在图中搜索一个长度为N的路径,且路径上的单词正好能够填在N个空里。
我们要在图上进行搜索,枚举可能的答案,因此可以使用DFS+回溯的思想来进行搜索。
同时由于题目有很多限制,我们可以在搜索过程中进行剪枝,来提高效率。

python代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution:

def exist(self, board: List[List[str]], word: str) -> bool:
N = len(word)
row = len(board)
col = len(board[0])
res = False

def backtrack(n, r, c, ans): # n表示空位下标,即目前要搜索的目标是word[n]这个字符。r,c分别表示当前要访问的行列号,ans表示当前的答案
nonlocal res
if word == ans: # 终止条件:找到了答案,则对res进行标记。
res = True
return
if res: # 剪枝1:如果已经找到了一个答案,就不找了
return
if r>=row or r<0 or c>=col or c<0 or n>=N: # 剪枝2:对于行列需要在图内,且如果当前答案长度已经超过目标长度,肯定不符合
return
if board[r][c] == 0: # 剪枝3:如果该位置已经访问过,则不再访问。(一个单元格不能重复使用)
return
if board[r][c] == word[n]: # 剪枝4:如果当前位置是要找的目标字符,才进行访问
ans += board[r][c]
temp = board[r][c] # 使用temp临时标记该位置的元素,然后将该位置置0,表示已经访问过
board[r][c] = 0

# dfs 搜索相邻位置
backtrack(n+1, r+1, c, ans)
backtrack(n+1, r-1, c, ans)
backtrack(n+1, r, c+1, ans)
backtrack(n+1, r, c-1, ans)
ans = ans[:-1] # 回退
board[r][c] = temp # 回复该位置的值,表示该位置还没有被访问过

# 从第一个字符匹配的位置开始搜索
for i in range(row):
for j in range(col):
if board[i][j] == word[0]:
backtrack(0, i, j, "")
return res