回溯
回溯算法理论基础
题目分类:
回溯法也可以叫做回溯搜索法,它是一种搜索的方式。回溯是递归的副产品,只要有递归就会有回溯。
回溯法的效率
虽然回溯法很难,很不好理解,但是回溯法并不是什么高效的算法。因为回溯的本质是穷举,穷举所有可能,然后选出我们想要的答案,如果想让回溯法高效一些,可以加一些剪枝的操作,但也改不了回溯法就是穷举的本质。
组合无序,排列有序
理解回溯法
所有回溯法的问题都可以抽象为树形结构,因为回溯法解决的都是在集合中递归查找子集,集合的大小就构成了树的宽度,递归的深度就构成了树的深度。
递归要有终止条件,所以必然是一棵高度有限的树(N 叉树)。
回溯法模板
回溯三部曲:
- 返回值以及参数 函数返回值一般为 void,参数一般是先写逻辑才能确定
- 终止条件 终止条件从树中就可以看出,一般来说是搜到叶子节点
- 遍历过程 一般是在集合中递归搜索,集合的大小构成了树的宽度,递归的深度构成的树的深度
第 77 题. 组合
给定两个整数 n 和 k,返回 1 ... n 中所有可能的 k 个数的组合。
示例: 输入: n = 4, k = 2 输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]
解答:
class Solution {
List<List<Integer>> res = new ArrayList<>();
Deque<Integer> deque = new LinkedList<>();
public List<List<Integer>> combine(int n, int k) {
backtracking(n, k, 1);
return res;
}
private void backtracking(int n, int k, int startindex){
if(deque.size() == k){
res.add(new ArrayList<>(deque));
return;
}
for(int i = startindex; i <= n - (k - deque.size() - 1); i++){
deque.offer(i);
backtracking(n, k, i+1);
deque.pollLast();
}
}
}
216.组合总和 III
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数,并且每种组合中不存在重复的数字。
说明:
- 所有数字都是正整数。
- 解集不能包含重复的组合。
解答:
class Solution {
List<List<Integer>> res = new ArrayList<>();
Deque<Integer> deque = new LinkedList<>();
public List<List<Integer>> combinationSum3(int k, int n) {
backtracking(k, n, 1);
return res;
}
private void backtracking(int k, int n, int startindex){
if(k == 0 || n == 0){
if(k == 0 && n == 0) res.add(new ArrayList<>(deque));
return;
}
for(int i = startindex; i <= Math.min(n, 9); i++){
deque.offer(i);
backtracking(k-1, n-i, i+1);
deque.pollLast();
}
}
}
17.电话号码的字母组合
给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。
给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。
解答:
class Solution {
List<String> res = new ArrayList<>();
StringBuilder temp = new StringBuilder();
public List<String> letterCombinations(String digits) {
if(digits == null || digits.length() == 0) return res;
String[] s = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
backtracking(digits, 0, s);
return res;
}
private void backtracking(String digits, int num, String[] s){
if(num == digits.length()){
res.add(temp.toString());
return;
}
String str = s[digits.charAt(num) - '0'];
for(int i = 0; i < str.length(); i++){
temp.append(str.charAt(i));
backtracking(digits, num + 1, s);
temp.deleteCharAt(temp.length() - 1);
}
}
}
39. 组合总和
给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明:
- 所有数字(包括 target)都是正整数。
- 解集不能包含重复的组合。
解答:
class Solution {
List<List<Integer>> res = new ArrayList<>();
List<Integer> temp = new ArrayList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
if(candidates == null || candidates.length == 0) return null;
backtracking(candidates, target, 0);
return res;
}
private void backtracking(int[] candidates, int target, int startindex){
if(target < 0){
return;
} else if(target == 0){
res.add(new ArrayList<>(temp));
return;
}
for(int i = startindex; i < candidates.length; i++){
temp.add(candidates[i]);
backtracking(candidates, target-candidates[i], i);
temp.remove(temp.size() - 1);
}
}
}
40.组合总和 II
给定一个数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明: 所有数字(包括目标数)都是正整数。解集不能包含重复的组合。
解答:
// used数组
class Solution {
List<List<Integer>> res = new ArrayList<>();
LinkedList<Integer> temp = new LinkedList<>();
boolean[] used;
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
if(candidates == null || candidates.length == 0) return null;
used = new boolean[candidates.length];
// 加标志数组,用来辅助判断同层节点是否已经遍历
Arrays.fill(used, false);
Arrays.sort(candidates);
backtracking(candidates, target, 0);
return res;
}
private void backtracking(int[] candidates, int target, int startindex){
if(target < 0){
return;
} else if(target == 0){
res.add(new ArrayList<>(temp));
return;
}
for(int i = startindex; i < candidates.length; i++){
// used[i - 1] == true,说明同⼀树⽀nums[i - 1]使⽤过
// used[i - 1] == false,说明同⼀树层nums[i - 1]使⽤过
// 如果同⼀树层nums[i - 1]使⽤过则直接跳过
if(i > 0 && candidates[i] == candidates[i-1] && !used[i-1]) continue;
temp.add(candidates[i]);
used[i] = true;
// 每个节点仅能选择一次,所以从下一位开始
backtracking(candidates, target-candidates[i], i+1);
used[i] = false;
temp.removeLast();
}
}
}
// 不用used数组
class Solution {
List<List<Integer>> res = new ArrayList<>();
LinkedList<Integer> temp = new LinkedList<>();
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
if(candidates == null || candidates.length == 0) return null;
Arrays.sort(candidates);
backtracking(candidates, target, 0);
return res;
}
private void backtracking(int[] candidates, int target, int startindex){
if(target < 0){
return;
} else if(target == 0){
res.add(new ArrayList<>(temp));
return;
}
for(int i = startindex; i < candidates.length; i++){
if(i > startindex && candidates[i] == candidates[i-1]) continue;// 要对同一树层使用过的元素进行跳过
temp.add(candidates[i]);
backtracking(candidates, target-candidates[i], i+1);
temp.removeLast();
}
}
}
131.分割回文串
给定一个字符串 s,将 s 分割成一些子串,使每个子串都是回文串。
返回 s 所有可能的分割方案。
解答:
class Solution {
List<List<String>> res = new ArrayList<>();
Deque<String> deque = new LinkedList<>();
public List<List<String>> partition(String s) {
if(s == null || s.length() == 0) return null;
backtracking(s);
return res;
}
private void backtracking(String s){
if(s == null){
res.add(new ArrayList(deque));
return;
}
int len1 = s.length();
for(int i = 0; i < len1; i++){
if(ishuiwen(s.substring(0,i+1))){
deque.offer(s.substring(0,i+1));
if(i+1 < len1) backtracking(s.substring(i+1,len1));
else backtracking(null);
deque.pollLast();
}
}
}
private boolean ishuiwen(String s){
int len = s.length();
for(int i = 0; i < len/2; i++){
if(s.charAt(i) != s.charAt(len - i - 1)) return false;
}
return true;
}
}
93.复原 IP 地址
给定一个只包含数字的字符串,复原它并返回所有可能的 IP 地址格式。
有效的 IP 地址 正好由四个整数(每个整数位于 0 到 255 之间组成,且不能含有前导 0),整数之间用 '.' 分隔。
解答:
class Solution {
List<String> res = new ArrayList<>();
public List<String> restoreIpAddresses(String s) {
StringBuilder sb = new StringBuilder(s);
backtracking(sb, 0, 0);
return res;
}
private void backtracking(StringBuilder s, int startindex, int pointnum){
if(pointnum == 3 && check(s, startindex, s.length())){
res.add(s.toString());
return;
}
if(pointnum > 3) return;
for(int i = startindex; i < s.length() && i < startindex + 3; i++){
if(check(s, startindex, i+1)){
s.insert(i+1,".");
backtracking(s, i+2, pointnum+1);
s.deleteCharAt(i+1);
}
}
}
private boolean check(StringBuilder s, int start, int end){
if(end-start > 3 || end > s.length() || start >= end || Integer.valueOf(s.substring(start, end)) > 255) return false;
if(s.charAt(start) == '0' && end-start > 1) return false;
return true;
}
}
78.子集
给定一组不含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。
说明:解集不能包含重复的子集。
解答:
class Solution {
List<List<Integer>> res = new ArrayList<>();
List<Integer> temp = new ArrayList<>();
public List<List<Integer>> subsets(int[] nums) {
if(nums == null || nums.length == 0) return null;
backtracking(nums, 0, nums.length-1);
return res;
}
private void backtracking(int[] nums, int left, int right){
if(left > right){
res.add(new ArrayList(temp));
return;
}
temp.add(nums[left]);
backtracking(nums, left+1, right);//添加nums[left]元素的集合
temp.removeLast();
backtracking(nums, left+1, right);//不添加nums[left]元素的集合
}
}
90.子集 II
给定一个可能包含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。
说明:解集不能包含重复的子集。
解答:
class Solution {
List<List<Integer>> res = new ArrayList<>();
List<Integer> temp = new ArrayList<>();
public List<List<Integer>> subsetsWithDup(int[] nums) {
if(nums == null || nums.length == 0) return null;
Arrays.sort(nums);
backtracking(nums, 0);
return res;
}
private void backtracking(int[] nums, int startindex){
res.add(new ArrayList(temp));//「遍历这个树的时候,把所有节点都记录下来,就是要求的子集集合」
//停止条件就是:i < nums.length
for(int i = startindex; i < nums.length; i++){
if(i > startindex && nums[i] == nums[i-1]) continue;
temp.add(nums[i]);
backtracking(nums, i+1);
temp.removeLast();
}
}
}
491.递增子序列
给定一个整型数组, 你的任务是找到所有该数组的递增子序列,递增子序列的长度至少是 2。
解答:
// 暴力判断重复
class Solution {
List<List<Integer>> res = new ArrayList<>();
List<Integer> temp = new ArrayList<>();
public List<List<Integer>> findSubsequences(int[] nums) {
if(nums == null || nums.length == 0) return null;
backtracking(nums, 0);
return res;
}
private void backtracking(int[] nums, int startindex){
if(temp.size() > 1){
if(temp.get(temp.size()-1) < temp.get(temp.size()-2)) return;
res.add(new ArrayList(temp));
}
for(int i = startindex; i < nums.length; i++){
boolean flag = false;//判断全集是否包含相同的元素
for(int j = i-1; j >= startindex; j--){
if(nums[i] == nums[j]){
flag = true;
break;
}
}
if(flag) continue;
temp.add(nums[i]);
backtracking(nums, i+1);
temp.removeLast();
}
}
}
// Map
class Solution {
List<List<Integer>> res = new ArrayList<>();
List<Integer> temp = new ArrayList<>();
public List<List<Integer>> findSubsequences(int[] nums) {
if(nums == null || nums.length == 0) return null;
backtracking(nums, 0);
return res;
}
private void backtracking(int[] nums, int startindex){
if(temp.size() > 1){
if(temp.get(temp.size()-1) < temp.get(temp.size()-2)) return;
res.add(new ArrayList(temp));
}
Map<Integer, Integer> map = new HashMap<>();
for(int i = startindex; i < nums.length; i++){
if(map.getOrDefault(nums[i], 0) > 0) continue;
map.put(nums[i], 1);
temp.add(nums[i]);
backtracking(nums, i+1);
temp.removeLast();
}
}
}
46.全排列
给定一个 没有重复 数字的序列,返回其所有可能的全排列。
解答:
class Solution {
List<List<Integer>> res = new ArrayList<>();
List<Integer> temp = new ArrayList<>();
public List<List<Integer>> permute(int[] nums) {
if(nums == null || nums.length == 0) return null;
List<Integer> nums1 = new ArrayList<>();
for(int i = 0; i < nums.length; i++) nums1.add(nums[i]);
backtracking(nums1);
return res;
}
private void backtracking(List<Integer> nums1){
if(nums1.size() ==0) res.add(new ArrayList(temp));
for(int i = 0; i < nums1.size(); i++){
temp.add(nums1.remove(i));
backtracking(nums1);
nums1.add(i, temp.remove(temp.size()-1));
}
}
}
47. 全排列 II
给定一个可包含重复数字的序列 nums ,按任意顺序 返回所有不重复的全排列。
解答:
class Solution {
List<List<Integer>> res = new ArrayList<>();
List<Integer> temp = new ArrayList<>();
public List<List<Integer>> permuteUnique(int[] nums) {
if(nums == null || nums.length == 0) return null;
Arrays.sort(nums);
List<Integer> nums1 = new ArrayList<>();
for(int i = 0; i < nums.length; i++) nums1.add(nums[i]);
backtracking(nums1);
return res;
}
private void backtracking(List<Integer> nums1){
if(nums1.size() ==0) res.add(new ArrayList(temp));
for(int i = 0; i < nums1.size(); i++){
if(i > 0 && nums1.get(i) == nums1.get(i-1)) continue;
temp.add(nums1.remove(i));
backtracking(nums1);
nums1.add(i, temp.remove(temp.size()-1));
}
}
}
回溯算法去重问题的另一种写法
两种写法的性能分析
HashSet<Integer> hashSet = new HashSet<>();//层去重
...
if (hashSet.contains(nums[i])) continue;
hashSet.add(nums[i]);//记录元素
需要注意的是:使用 set 去重的版本相对于 used 数组的版本效率都要低很多。
原因在回溯算法:递增子序列 中也分析过,主要是因为程序运行的时候对 unordered_set 频繁的 insert,unordered_set 需要做哈希映射(也就是把 key 通过 hash function 映射为唯一的哈希值)相对费时间,而且 insert 的时候其底层的符号表也要做相应的扩充,也是费时的。
而使用 used 数组在时间复杂度上几乎没有额外负担!
使用 set 去重,不仅时间复杂度高了,空间复杂度也高了,在本周小结!(回溯算法系列三) 中分析过,组合,子集,排列问题的空间复杂度都是 O(n),但如果使用 set 去重,空间复杂度就变成了 O(n^2),因为每一层递归都有一个 set 集合,系统栈空间是 n,每一个空间都有 set 集合。
used 数组可是全局变量,每层与每层之间公用一个 used 数组,所以空间复杂度是 O(n + n),最终空间复杂度还是 O(n)。
332.重新安排行程
给定一个机票的字符串二维数组 [from, to],子数组中的两个成员分别表示飞机出发和降落的机场地点,对该行程进行重新规划排序。所有这些机票都属于一个从 JFK(肯尼迪国际机场)出发的先生,所以该行程必须从 JFK 开始。
提示:
- 如果存在多种有效的行程,请你按字符自然排序返回最小的行程组合。例如,行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小,排序更靠前
- 所有的机场都用三个大写字母表示(机场代码)。
- 假定所有机票至少存在一种合理的行程。
- 所有的机票必须都用一次 且 只能用一次。
解答:
class Solution {
ArrayList<String> res = new ArrayList<>();
Deque<String> deque = new LinkedList<>();
public List<String> findItinerary(List<List<String>> tickets) {
Collections.sort(tickets, (a, b) -> a.get(1).compareTo(b.get(1)));//排序
deque.offer("JFK");
bakctracking(tickets);
return res;
}
private void bakctracking(List<List<String>> tickets){
if(tickets == null || tickets.size() == 0){
ArrayList<String> temp = new ArrayList<>(deque);
res.addAll(temp);
return;
}
Set<String> set = new HashSet<>();
for(int i = 0; i < tickets.size(); i++){
if(res.size() > 0) return;
List<String> s = tickets.get(i);
if(deque.peekLast().equals(s.get(0)) && set.add(s.get(1))){
set.add(s.get(1));
deque.offer(s.get(1));
tickets.remove(i);
bakctracking(tickets);
tickets.add(i, s);
deque.pollLast();
}
}
}
}
51. N 皇后
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。
给你一个整数 n ,返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案,该方案中 'Q' 和 '.' 分别代表了皇后和空位。
解答:
class Solution {
List<List<String>> res = new ArrayList<>();
char[][] chessboard;
public List<List<String>> solveNQueens(int n) {
chessboard = new char[n][n];
for(char[] c : chessboard){
Arrays.fill(c, '.');
}
backtracking(0, n, chessboard);
return res;
}
private void backtracking(int row, int n, char[][] chessboard){
if(row == n){
List<String> list = new ArrayList<>();
for(char[] c : chessboard){
list.add(String.valueOf(c));
}
res.add(list);
return;
}
for(int i = 0; i < n; i++){//树的每一层遍历行
if(isvalid(row, i, n, chessboard)){
chessboard[row][i] = 'Q';
backtracking(row+1, n, chessboard);
chessboard[row][i] = '.';
}
}
}
private boolean isvalid(int row, int col, int n, char[][] chessboard){
//检查列
for(int i = 0; i < row; i++){
if(chessboard[i][col] == 'Q') return false;
}
//45°
for(int i = row, j = col; i >= 0 && j < n; i--, j++){
if(chessboard[i][j] == 'Q') return false;
}
//135°
for(int i = row, j = col; i >= 0 && j >= 0; i--, j--){
if(chessboard[i][j] == 'Q') return false;
}
return true;
}
}
37. 解数独
编写一个程序,通过填充空格来解决数独问题。
解答:
class Solution {
// 二进制中1表示 对应位置已经有值了
private int[] rows = new int[9];
private int[] cols = new int[9];
private int[][] cells = new int[3][3];
boolean flag = false;
public void solveSudoku(char[][] board) {
int cnt = 0;
for(int i = 0; i < 9; i++){
for(int j = 0; j < 9; j++){
char c = board[i][j];
if(c == '.'){
cnt++;
} else {
int n = c - '1';
fillNumber(i, j, n, true);
}
}
}
backtracking(cnt, board);
}
private void backtracking(int cnt, char[][] board){
if(cnt == 0){
flag = true;
return;
}
// 获取候选数最少的位置
int[] pos = getMinposition(board);
int row = pos[0], col = pos[1];
int rest = ~(rows[row] | cols[col] | cells[row/3][col/3]) & ((1<<9) - 1);// 添加掩码,因为int是32位的!!!
for(int i = 0; i < 9; i++){
if((rest & (1 << i)) != 0){
fillNumber(row, col, i, true);
board[row][col] = (char)(i+1+'0');
backtracking(cnt-1, board);
if(flag) return;
board[row][col] = '.';
fillNumber(row, col, i, false);
}
}
}
// 获取候选项最少的位置
private int[] getMinposition(char[][] board){
int[] res = new int[2];
int min = 10;
for(int i = 0; i < 9; i++){
for(int j = 0; j < 9; j++){
if(board[i][j] == '.'){
int rest = ~(rows[i] | cols[j] | cells[i/3][j/3]) & ((1<<9) - 1);
int count = getCount(rest);
if(count < min){
min = count;
res[0] = i;
res[1] = j;
}
if(min == 1) return res;// 找到最优解直接返回
}
}
}
return res;
}
//得到1的个数
private int getCount(int rest){
int count = 0;
while(rest != 0){
count += rest & 1;
rest = rest >> 1;
}
return count;
}
private void fillNumber(int x, int y, int n, boolean fill){
// ture set 1, false set 0
rows[x] = fill ? rows[x] | (1<<n) : rows[x] & ~(1<<n);
cols[y] = fill ? cols[y] | (1<<n) : cols[y] & ~(1<<n);
cells[x/3][y/3] = fill ? cells[x/3][y/3] | (1<<n) : cells[x/3][y/3] & ~(1<<n);
}
}
306. 累加数
累加数 是一个字符串,组成它的数字可以形成累加序列。
一个有效的 累加序列 必须 至少 包含 3 个数。除了最开始的两个数以外,序列中的每个后续数字必须是它之前两个数字之和。
给你一个只包含数字 '0'-'9'
的字符串,编写一个算法来判断给定输入是否是 累加数 。如果是,返回 true
;否则,返回 false
。
**说明:**累加序列里的数,除数字 0 之外,不会 以 0 开头,所以不会出现 1, 2, 03
或者 1, 02, 3
的情况。
解答:
class Solution {
String num_temp;
int n;
List<List<Integer>> list = new ArrayList<>(); // store all the possible numbers
public boolean isAdditiveNumber(String num) {
n = num.length();
num_temp = num;
return dfs(num_temp, 0);
}
public boolean dfs(String num, int index){
int m = list.size();
if(index == n) return m >= 3; // back
int max = num.charAt(index) - '0' == 0 ? index + 1 : n; // the hightest index of the current number should be more than zero
List<Integer> cur = new ArrayList<>(); // store the third number
for(int i = index; i < max; i++){
cur.add(0, num.charAt(i) - '0');
if(m < 2 || check(list.get(m-1), list.get(m-2), cur)){ // only there are at least three numbers in the list and the current number can be added to the previous two numbers
list.add(cur);
if(dfs(num, i+1)) return true;
list.remove(list.size() - 1);
}
}
return false;
}
public boolean check(List<Integer> a, List<Integer> b, List<Integer> c){ // check if a+b=c
int t = 0; // store the sum of a and b
List<Integer> res = new ArrayList<>();
for(int i = 0; i < a.size() || i < b.size(); i++){
if(i < a.size()) t += a.get(i);
if(i < b.size()) t += b.get(i);
res.add(t%10);
t /= 10;
}
if(t > 0) res.add(t);
boolean flag = res.size() == c.size();
for(int i = 0; i < c.size() && flag; i++){
if(res.get(i)!= c.get(i)) flag = false;
}
return flag;
}
}
总结
其他
17. 电话号码的字母组合
给定一个仅包含数字 2-9
的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。
解答:
MAPPING = "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
n = len(digits)
if n == 0:
return []
res = []
path = [''] * n
def dfs(i: int) -> None:
if i == n:
res.append(''.join(path))
return
for c in MAPPING[int(digits[i])]:
path[i] = c
dfs(i+1)
dfs(0)
return res
22. 括号生成
数字 n
代表生 成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。
解答:
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
left = 0
res = []
def dfs(str1: int) -> None:
nonlocal left, n, res
if n == 0:
res.append(str1)
return
if left < n: # 是否可添加左括号
str1 += "("
left += 1
dfs(str1)
left -= 1
str1 = str1[:-1]
if left > 0: # 是否可添加右括号
str1 += ")"
left -= 1
n -= 1
dfs(str1)
left += 1
n += 1
str1 = str1[:-1]
dfs("")
return res
# 灵神
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
m = 2 * n
path = [''] * m
res = []
def dfs(i: int, left: int) -> None:
if i == m:
res.append(''.join(path))
return
if left < n:
path[i] = '('
dfs(i+1, left+1)
if (2 * left) >= (i + 1):
path[i] = ')' # 直接覆盖
dfs(i+1, left)
dfs(0, 0)
return res
复杂度分析
-
时间复杂度:分析回溯问题的时间复杂度,有一个通用公式:路径长度×搜索树的叶子数。对于本题,它等于。但由于左右括号的约束,实际上没有这么多叶子,根据 Catalan 数,只有个叶子节点,所以实际的时间复杂度为 。此外,根据阶乘的 Stirling 公式,时间复杂度也可以表示为 。
-
空间复杂度:O(n)。返回值的空间不计入。
79. 单词搜索
给定一个 m x n
二维字符网格 board
和一个字符串单词 word
。如果 word
存在于网格中,返回 true
;否则,返回 false
。
单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
解答:
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
m = len(board)
n = len(board[0])
l = len(word)
visited = [[0]*n for _ in range(m)]
cnt = Counter(c for row in board for c in row)
if not cnt >= Counter(word): # 优化
return False
if cnt[word[-1]] < cnt[word[0]]: # 天才啊,优化路径数
word = word[::-1]
def dfs(idx: int, i: int, j: int) -> bool:
if idx == l:
return True
if i < 0 or i >= m or j < 0 or j >= n:
return False
if visited[i][j] == 0 and word[idx] == board[i][j]:
visited[i][j] = 1
if dfs(idx+1, i, j+1) or dfs(idx+1, i, j-1) or dfs(idx+1, i+1, j) or dfs(idx+1, i-1, j):
return True
visited[i][j] = 0
return False
for i, row in enumerate(board):
for j, x in enumerate(row):
if word[0] == x and dfs(0, i, j):
return True
return False
复杂度分析
- 时间复杂度:,其中 m 和 n 分别为 grid 的行数和列数,k 是 word 的长度。除了递归入口,其余递归至多有 3 个分支(因为至少有一个方向是之前走过的),所以每次递归(回溯)的时间复杂度为 ,一共回溯 次,所以时间复杂度为 。
- 空间复杂度:。其中 是字符集合的大小。递归需要 的栈空间。部分语言用的数组代替哈希表,可以视作 。
394. 字符串解码
给定一个经过编码的字符串,返回它解码后的字符串。
编码规则为: k[encoded_string]
,表示其中方括号内部的 encoded_string
正好重复 k
次。注意 k
保证为正整数。
你可以认为输入字符串总是有效的;输入字符串中没有额外的空格,且输入的方括号总是符合格式要求的。
此外,你可以认为原始数据不包含数字,所有的数字只表示重复的次数 k
,例如不会出现像 3a
或 2[4]
的输入。
解答:
class Solution:
def decodeString(self, s: str) -> str:
n = len(s)
next_i = 0
def dfs(start: int) -> str:
if start >= n:
return ""
res = ""
num = 0
nonlocal next_i
i = start
while start <= i < n:
while start <= i < n and 0 <= ord(s[i]) - ord('a') <= 25:
res += s[i]
i += 1
if i >= n: # 字母结束后可能就结尾了
break
while 0 <= ord(s[i]) - ord('0') <= 9: # 数字和字母的顺序不能乱
num = 10 * num + ord(s[i]) - ord('0')
i += 1
if ord(s[i]) == ord(']'):
next_i = i
break
if ord(s[i]) == ord('['):
print(num)
res += num * dfs(i+1)
i = next_i
num = 0
i += 1
return res
return dfs(0)