跳至主要內容

hot150-12-回溯

holic-x...大约 19 分钟算法算法

难度说明：🟢简单🟡中等🔴困难

hot150-12-回溯

​ 题目中涉及到所有组合字眼，思考是否可以通过回溯解决

  • 回溯算法核心（学会画树）

    • 如果解决一个问题有多个步骤，每一个步骤有多种方法，题目又要找出所有的方法，可以使用回溯算法；
    • 回溯算法是在一棵树上的 深度优先遍历（因为要找所有的解，所以需要遍历）；
    • 组合问题，相对于排列问题而言，不计较一个组合内元素的顺序性（即 [1, 2, 3] 与 [1, 3, 2] 认为是同一个组合），因此很多时候需要按某种顺序展开搜索，这样才能做到不重不漏

  • 回溯算法基本模板

    // todo
public void backTrack(){
    // 1.递归出口（返回限定或者将满足条件的内容加入结果集合）
    if(xxx){ // 满足递归条件
        xxx.add(x); // 加入结果集
        return ;
    }
    
    // 2.执行操作（例如字符串拼接）
    buffer.add(); // 尝试操作
    backTrack(); // 递归
    buffer.remove(buffer.length() - 1); // 复原现场

}

🟡01-电话号码的字母组合（17）

1.题目内容

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

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

示例 1：

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

示例 2：

输入：digits = ""
输出：[]

示例 3：

输入：digits = "2"
输出：["a","b","c"]

2.题解思路

👻方法1：队列法

  • 思路分析：三层循环嵌套：遍历digits （获取数字映射的字符集）=> 遍历队列（当前队列，需记录当前size） => 遍历字符映射集合（拼接并加入队列）
    • （1）构建数字和字母的映射
    • （2）遍历digits的每个数字元素，然后通过队列存储字符串变化的过程：以23为例
      • 初始化队列为空[""]
      • 遍历数字2（对应abc）：取出目前队列中的所有元素，分别与abc这三个字符进行拼接，然后重新放回队列，等待下次拼接
        • 完成后，队列更新为：a、b、c
      • 遍历数字3（对应def）：取出目前队列中的所有元素，分别与def这三个字符进行拼接，然后重新放回队列，等待下次拼接
        • 完成后，队列更新为：ad、ae、af、bd、be、bf、cd、ce、cf
      • 数字遍历完成，最终返回队列
// 队列法：遍历每个数字，将每次遍历拼接后的结果存入队列，每次遍历的时候从队列中取出所有元素进行拼接然后重新放入队列
public List<String> letterCombinations(String digits) {
    Map<Integer, String> map = new HashMap<>();
    map.put(2, "abc");
    map.put(3, "def");
    map.put(4, "ghi");
    map.put(5, "jkl");
    map.put(6, "mno");
    map.put(7, "pqrs");
    map.put(8, "tuv");
    map.put(9, "wxyz");

    // 空字符串验证
    if (digits == null || "".equals(digits)) {
        return new ArrayList<>();
    }

    // 定义队列存储字符串的变化过程
    List<String> list = new ArrayList<>();
    list.add("");// 初始化一个空字符串入队

    // 遍历数组元素，获取到每个数字，然后组合拼接
    for (int i = 0; i < digits.length(); i++) {
        // 获取到对应数字及其字母映射
        int idx = digits.charAt(i) - '0';
        String str = map.get(idx);
        // 遍历映射的字符串，从队列中依次取出元素进行拼接，随后重新装入队列，等待下次拼接
        int listSize = list.size(); // 记录当前list集合大小（后续需要将组装的string加入队尾，此处只遍历到目前的队列大小为止）
        for (int j = 0; j < listSize; j++) {
            // 取出队首元素
            String findFirst = list.remove(0);
            // 分别拼接字符，然后入队
            for (int k = 0; k < str.length(); k++) {
                list.add(findFirst + str.charAt(k));
            }
        }
    }

    // 返回最终结果
    return list;
}

  • 复杂度分析

    • 时间复杂度：O（3M × 4N）（M 三个字母的数字个数，N4个字母的数字个数）

    • 空间复杂度：O（3M × 4N）（一共生成3M × 4N个结果，空间占用取决于队列占用）

👻方法2：回溯法

  • 思路分析：深度优先搜索思路：Map + 回溯
image-20241105170503704
/**
 * 17 电话号码的字母组合
 */
public class Solution2 {
    // 定义数字和字母映射集合
    Map<Integer, String> map = new HashMap<Integer, String>() {{
        put(2, "abc");
        put(3, "def");
        put(4, "ghi");
        put(5, "jkl");
        put(6, "mno");
        put(7, "pqrs");
        put(8, "tuv");
        put(9, "wxyz");
    }};

    List<String> ans = new ArrayList<>();
    StringBuffer buffer = new StringBuffer(); // 定义一个字符串，用于跟踪回溯方法调用过程中的字符串

    /**
     * 定义回溯方法: digits 要处理的字符串，idx 当前处理的位置
     */
    public void backTrack(String digits, int idx) {
        // 如果处理位置和字符串长度相等，说明拼接完成（路径完整）
        if (idx == digits.length()) {
            ans.add(buffer.toString()); // 加入结果集
        }else{
            // 否则继续拼接指定数字对应的字符
            String letters = map.get(digits.charAt(idx) - '0'); // 字符转数字
            for (int i = 0; i < letters.length(); i++) {
                buffer.append(letters.charAt(i)); // 将当前字母添加到目前的组合中
                backTrack(digits, idx + 1);// 递归找出剩余数字的所有字母组合（idx+1 表示指向下一个数字）
                buffer.deleteCharAt(idx); // 回溯：删除当前字母，便于尝试下个字母（剪枝）
            }
        }
    }

    // 回溯法：深度优先遍历思想（Map+回溯）
    public List<String> letterCombinations(String digits) {
        // 空字符串验证
        if(digits==null||"".equals(digits)){
            return new ArrayList<>();
        }

        // 字符串不为空，执行方法
        backTrack(digits, 0);
        return ans;
    }

}

  • 复杂度分析

    • 时间复杂度：O（3M × 4N）（M 三个字母的数字个数，N4个字母的数字个数）

    • 空间复杂度：O（3M × 4N）（一共生成3M × 4N个结果，空间占用取决于队列占用）

🟡02-组合（77）

1.题目内容

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

2.题解思路

👻方法1：回溯+剪枝

/**
 * 077 组合
 */
public class Solution1 {

    // 全局定义返回结果
    List<List<Integer>> ans = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>(); // 借助队列存储遍历路径的临时结果

    // 回溯方法定义：idx 指向当前可遍历的索引起点
    public void backTrack(int idx, int n, int k) {
        // 当有k个数则加入结果集（递归终止条件：path的长度达到k）
        if (k == path.size()) {
            ans.add(new ArrayList<>(path)); // new 一个队列（如果传入的path是地址，后面对path的修改也会体现，因此此处是new）
            return;
        }
        // 从[i,n]中递归（遍历可能的搜索起点：idx开始）
        for (int i = idx; i <= n; i++) { // todo 优化：i <= n - (k - path.size()) + 1;
            path.add(i); // 添加
            backTrack(i + 1, n, k); // 递归（设置搜索起点+1，因为组合中不允许出现重复的元素）
            path.removeLast(); // 逆向操作（深度优先遍历有回头的过程，递归之前做了什么，递归之后此处需要做同操作的逆向操作）
        }
    }

    // 回溯法
    public List<List<Integer>> combine(int n, int k) {
        // 特例：如果k<=0或者n<k 返回空集合
        // 其他情况进行递归
        backTrack(1, n, k); // 设定从1开始遍历
        return ans;
    }

}

  • 复杂度分析

    • 时间复杂度：

    • 空间复杂度：

回溯分析：可以将path路径打印出来理解

/**
 * 077 组合
 */
public class Solution2 {

    // 全局定义返回结果
    List<List<Integer>> ans = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>(); // 借助队列存储遍历路径的临时结果

    // 回溯方法定义：idx 指向当前可遍历的索引起点
    public void backTrack(int idx, int n, int k) {
        // 当有k个数则加入结果集（递归终止条件：path的长度达到k）
        if (k == path.size()) {
            ans.add(new ArrayList<>(path)); // new 一个队列（如果传入的path是地址，后面对path的修改也会体现，因此此处是new）
            return;
        }
        // 从[i,n]中递归（遍历可能的搜索起点：idx开始）
        for (int i = idx; i <= n; i++) {
            path.add(i); // 添加
            System.out.println("------ 递归之前 ------ =>" + path);
            backTrack(i + 1, n, k); // 递归（设置搜索起点+1，因为组合中不允许出现重复的元素）
            path.removeLast(); // 逆向操作（深度优先遍历有回头的过程，递归之前做了什么，递归之后此处需要做同操作的逆向操作）
            System.out.println("------ 递归之后 ------ =>" + path);
        }
    }

    // 回溯法
    public List<List<Integer>> combine(int n, int k) {
        // 特例：如果k<=0或者n<k 返回空集合
        // 其他情况进行递归
        backTrack(1, n, k); // 设定从1开始遍历
        return ans;
    }

    public static void main(String[] args) {
        Solution2 solution = new Solution2();
        List<List<Integer>> ans = solution.combine(5,3);
        System.out.println("结果：" + ans);
    }

}

// output
------ 递归之前 ------ =>[1]
------ 递归之前 ------ =>[1, 2]
------ 递归之前 ------ =>[1, 2, 3]
------ 递归之后 ------ =>[1, 2]
------ 递归之前 ------ =>[1, 2, 4]
------ 递归之后 ------ =>[1, 2]
------ 递归之前 ------ =>[1, 2, 5]
------ 递归之后 ------ =>[1, 2]
------ 递归之后 ------ =>[1]
------ 递归之前 ------ =>[1, 3]
------ 递归之前 ------ =>[1, 3, 4]
------ 递归之后 ------ =>[1, 3]
------ 递归之前 ------ =>[1, 3, 5]
------ 递归之后 ------ =>[1, 3]
------ 递归之后 ------ =>[1]
------ 递归之前 ------ =>[1, 4]
------ 递归之前 ------ =>[1, 4, 5]
------ 递归之后 ------ =>[1, 4]
------ 递归之后 ------ =>[1]
------ 递归之前 ------ =>[1, 5]
------ 递归之后 ------ =>[1]
------ 递归之后 ------ =>[]
------ 递归之前 ------ =>[2]
------ 递归之前 ------ =>[2, 3]
------ 递归之前 ------ =>[2, 3, 4]
------ 递归之后 ------ =>[2, 3]
------ 递归之前 ------ =>[2, 3, 5]
------ 递归之后 ------ =>[2, 3]
------ 递归之后 ------ =>[2]
------ 递归之前 ------ =>[2, 4]
------ 递归之前 ------ =>[2, 4, 5]
------ 递归之后 ------ =>[2, 4]
------ 递归之后 ------ =>[2]
------ 递归之前 ------ =>[2, 5]
------ 递归之后 ------ =>[2]
------ 递归之后 ------ =>[]
------ 递归之前 ------ =>[3]
------ 递归之前 ------ =>[3, 4]
------ 递归之前 ------ =>[3, 4, 5]
------ 递归之后 ------ =>[3, 4]
------ 递归之后 ------ =>[3]
------ 递归之前 ------ =>[3, 5]
------ 递归之后 ------ =>[3]
------ 递归之后 ------ =>[]
------ 递归之前 ------ =>[4]
------ 递归之前 ------ =>[4, 5]
------ 递归之后 ------ =>[4]
------ 递归之后 ------ =>[]
------ 递归之前 ------ =>[5]
------ 递归之后 ------ =>[]
结果：[[1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 3, 4], [1, 3, 5], [1, 4, 5], [2, 3, 4], [2, 3, 5], [2, 4, 5], [3, 4, 5]]

🟡03-全排列（46）

1.题目内容

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

2.题解思路

👻方法1：回溯

  • 思路分析：dfs 深度优先遍历
  • 回溯的核心：交换元素位置（固定1位，递归交换）
class Solution {

    // 定义返回结果
    List<List<Integer>> res = new ArrayList<List<Integer>>();

    // 暴力思路：多层嵌套
    public List<List<Integer>> permute(int[] nums) {
        // 调用递归方法进行全排列（此处先将nums转化为List便于处理）
        List<Integer> numsList = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            numsList.add(nums[i]);
        }
        // 调用递归方法进行全排列
        dfs(numsList, 0);
        // 返回结果
        return res;
    }

    // 定义两个元素交换的方法
    public void swap(List<Integer> nums, int i, int j) {
        int temp = nums.get(i);
        nums.set(i, nums.get(j));
        nums.set(j, temp);
    }

    // 定义dfs遍历方式
    public void dfs(List<Integer> nums, int idx) {
        // 递归出口，遍历到数组尾部结束
        if (idx == nums.size() - 1) {
            res.add(new ArrayList<>(nums)); // 添加排列方案(此处需new一个，否则添加的是引用)
            return; // 退出当前方法
        }
        // 执行操作
        for (int i = idx; i < nums.size(); i++) {
            // 核心操作：交换（将nums[i]固定在x的位置）、进行全排列算法、复原（通过再次交换，还原成原来的数组便于下一次进行排列）
            swap(nums, i, idx); // 交换 (Collections.swap(nums,i,idx);)
            dfs(nums, idx + 1); // 进行全排列算法
            swap(nums, i, idx); // 复原
        }
    }
}

  • 复杂度分析

    • 时间复杂度：O(n×n!)，其中 n 为序列的长度

    • 空间复杂度：O（n） 空间复杂度取决于递归的深度（除答案数组以外，递归函数在递归过程中需要为每一层递归函数分配栈空间，所以这里需要额外的空间且该空间取决于递归的深度）

🟡04-组合总和（39）

1.题目内容

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例 1：

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

示例 2：

输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3：

输入: candidates = [2], target = 1
输出: []

2.题解思路

👻方法1：回溯

/**
 * 039 组合总和
 */
public class Solution1 {

    List<List<Integer>> ans = new ArrayList<>(); // 结果集合
    LinkedList<Integer> path = new LinkedList<>(); // 路径列表
    int curSum = 0; // 记录当前path的元素之和

    /**
     * 回溯方法：
     * 递归出口：找到 target（加入结果集） 或者 当前集合元素之和比target大，则可直接剪枝
     */
    public void backTrack(int[] nums, int target, int idx) {
        // 找到满足的target
        if (curSum == target) {
            ans.add(new ArrayList<>(path)); // 此处需要new一个List
            return;
        }
        // 如果sum大于target则无需继续递归（剪枝）
        if (curSum > target) {
            return;
        }

        for (int i = idx; i < nums.length; i++) {
            // 尝试
            path.add(nums[i]);
            curSum += nums[i];

            backTrack(nums, target, i); // 递归

            // 复原现场
            path.removeLast();
            curSum -= nums[i];
        }
    }


    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        if (candidates == null || candidates.length == 0) {
            return new ArrayList<>();
        }
        // 递归检索组合
        backTrack(candidates, target, 0);
        return ans;
    }

}

  • 复杂度分析

    • 时间复杂度：

    • 空间复杂度：

代码参考版本

​ 此处版本是将公共的一些内容（属性）抽离出来，然后再进行dfs操作获取组合

class Solution {
    
    private List<List<Integer>> ans = new ArrayList<>();
    private List path = new ArrayList<>();
    private int[] candidates;
    private int target;

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        this.candidates = candidates;
        this.target = target;
        dfs(0, 0);
        return ans;
    }

    private void dfs(int start, int sum) {
        if (sum == target) {
            ans.add(new ArrayList<>(path));
            return;
        }
        if (sum > target) {
            return;
        }

        for (int i = start; i < candidates.length; i++) {
            path.add(candidates[i]);
            dfs(i, sum + candidates[i]);
            path.remove(path.size() - 1);
        }
    }

}

🔴05-N皇后II（52）

1.题目内容

2.题解思路

👻方法1：

  • 复杂度分析

    • 时间复杂度：

    • 空间复杂度：

🟡06-括号生成（22）

1.题目内容

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

2.题解思路

👻方法1：暴力法（序列生成+校验括号有效性）

  • 思路分析：生成所有可能的括号序列，然后校验这个序列的括号是否有效
    • 回溯方法辅助：
      • 参数初始化：List<String> ans 存储结果集、StringBuilder buffer 存储递归过程中的临时结果
      • 递归出口：当buffer的长度达到2×n（即n对括号的长度，buffer达到这个长度时需进一步校验括号序列是否满足条件，满足则加入ans）
      • 递归思路（回溯）：分别依次加入左括号（加入左括号，递归，复原现场）、右括号（加入右括号，递归，复原现场）
    • 核心方法：校验n的有效性（讨论临界条件），n>0则调用回溯方法进行序列生成、校验
/**
 * 022 括号生成
 */
public class Solution1 {

    List<String> ans = new ArrayList<>(); // 定义结果集
    StringBuilder buffer = new StringBuilder(); // 用于跟踪当前括号序列

    public List<String> generateParenthesis(int n) {
        if (n == 0) {
            return new ArrayList<>();
        }

        // n 不为0，递归遍历所有括号序列并校验序列的有效性
        generate(n);
        return ans;
    }

    // 定义辅助方法生成括号序列并校验序列的有效性
    public void generate(int n) {
        // 递归出口：当前序列长度等于2*n（n表示括号对数）
        if (buffer.length() == 2 * n) {
            // 校验括号序列是否有效
            if (isValid(buffer.toString())) {
                ans.add(buffer.toString());
            }
        } else {
            // 加入左括号或者右括号，然后深度遍历到底部校验括号序列
            buffer.append("("); // 尝试加入左括号
            generate(n);
            buffer.deleteCharAt(buffer.length() - 1); // 复原现场

            buffer.append(")"); // 尝试加入右括号
            generate(n);
            buffer.deleteCharAt(buffer.length() - 1); // 复原现场
        }
    }

    // 校验序列的括号有效性（balance）
    public boolean isValid(String str) {
        int balance = 0; // 定义平衡参数校验括号序列的有效性
        for (char c : str.toCharArray()) {
            if (c == '(') {
                balance++;
            } else if (c == ')') {
                balance--;
            }
            if (balance < 0) {
                return false;
            }
        }
        return balance == 0;
    }

}

  • 复杂度分析

    • 时间复杂度：O（22n n）这个过程中需要建立所有序列，并验证序列的有效性

    • 空间复杂度：O（n）空间占用取决于递归栈的深度（每一层递归函数需要O（1）的空间，最多递归2n层，空间复杂度为O（n））

👻方法2：回溯法（方法1版本优化）

  • 思路分析：整体思路和方法1版本中是一样的，此处根据左括号的个数来决定放右括号的个数（深度遍历，根据左括号的个数放右括号）
    • 递归出口：buffer.length() == 2 * n （在递归的过程中确保的括号序列生成的有效性，因此此处不需要再在递归出口中进行校验（作用相当于剪枝））
    • 递归过程：
      • left < n：判断左括号个数是否有n个，不足n则继续补左括号
      • right<left：判断右括号是否和左括号匹配，不足数量则继续补右括号
/**
 * 022 括号生成
 */
public class Solution2 {

    List<String> ans = new ArrayList<>(); // 定义结果集
    StringBuilder buffer = new StringBuilder(); // 用于跟踪当前括号序列

    public List<String> generateParenthesis(int n) {
        if (n == 0) {
            return new ArrayList<>();
        }

        // n 不为0，递归遍历所有括号序列并校验序列的有效性
        generate(n,0,0);
        return ans;
    }

    /**
     * 定义辅助方法生成括号序列并校验序列的有效性(优化点：根据左括号的个数来决定放右括号)
     * @param n     括号对数
     * @param left  左括号个数
     * @param right 右括号个数
     */
    public void generate(int n, int left, int right) {
        // 递归出口：当前序列长度等于2*n（n表示括号对数）
        if (buffer.length() == 2 * n) {
            // 在递归的过程中控制了括号序列的有序性，因此此处只需要校验对数是否满足
            ans.add(buffer.toString());
        } else {

            // 判断左括号是否有n个，如果不足则可以继续放左括号
            if (left < n) {
                buffer.append("("); // 尝试加入左括号
                generate(n, left + 1, right); // 递归
                buffer.deleteCharAt(buffer.length() - 1); // 复原现场
            }

            // 根据左括号校验右括号
            if (right < left) { // 如果右括号比左括号个数小，则继续补足左括号
                buffer.append(")"); // 尝试加入右括号
                generate(n, left, right + 1);
                buffer.deleteCharAt(buffer.length() - 1); // 复原现场
            }
        }
    }
}

  • 复杂度分析

    • 时间复杂度：

    • 空间复杂度：O（n）需要存储临时结果集

🟡07-单词搜索（79）

1.题目内容

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

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

image-20241106100015683

2.题解思路

👻方法1：回溯

参考题解学习open in new window

核心：循环遍历矩阵中每一个元素，由其为起点出发进行dfs操作（dfs的过程是为了判断是否存在word序列），校验结果即可

  • 终止条件：
    • 如果遇到边界、当前矩阵元素和目标字符不符、当前矩阵元素已经被访问过这几种情况则返回false
    • 如果遍历到目标字符串的最后一位则说明全部匹配，返回true
  • 递推工作：
    • 记录当前矩阵元素为cur，并将当前矩阵元素标记为已访问（例如'/0'）
    • 随后四个方向执行dfs操作（搜索下一单元格，向四个方向进行检索），如果四个方向中存在一个满足条件则直接返回（或操作，不需要全部找出）
    • 还原矩阵元素（将矩阵元素复原至原来的值）
/**
 * 079 单词搜索
 */
public class Solution1 {

    // 遍历二维矩阵的每个元素作为起点，确认其dfs是否存在路径满足匹配word序列
    public boolean exist(char[][] board, String word) {
        int m = board.length, n = board[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dfs(i, j, board, word, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    // 辅助方法构建字符序列
    public boolean dfs(int row, int col, char[][] board, String word, int idx) {
        // 结束条件（遇到边界（索引为负数或者超出长度）、当前元素与目标元素不符、当前元素已被访问则返回false；如果遍历到word的最后一位则说明存在匹配word则返回true）
        // 返回false的情况
        if (row >= board.length || row < 0 || col >= board[row].length || col < 0 || board[row][col] != word.charAt(idx) || board[row][col] == '0') {
            return false;
        }
        // 返回true的情况
        if (idx == word.length() - 1) {
            return true;
        }

        // 如果当前遍历元素和idx指向的word对应元素匹配则可继续进行检索判断下一个元素是否匹配（将元素进行标记，然后往4个方向进行判断）
        char cur = board[row][col]; // 记录当前值
        board[row][col] = '0'; // 将该值标记为已遍历
        // 分别向4个方向进行遍历（上下左右）
        if (dfs(row - 1, col, board, word, idx + 1) || dfs(row + 1, col, board, word, idx + 1)
                || dfs(row, col - 1, board, word, idx + 1) || dfs(row, col + 1, board, word, idx + 1)) {
            return true; // 如果四个方向中有一个方向满足，则继续往下
        }
        board[row][col] = cur; // 复原现场
        return false;
    }

}

  • 复杂度分析

    • 时间复杂度：最坏情况下需要遍历字符串长度为K的所有方案，时间复杂度为O（3KMN）（一共有M×N个起点，每个起点对应方案数为3K（dfs搜索中有4个方向可以选择，舍弃回头的上个字符的方向，剩下3种选择））

    • 空间复杂度：O(K) 递归深度不超过K，因此系统累计使用的栈空间占用为O(K)（因为函数返回之后，对应的栈空间也会释放），最坏情况下K=MN（递归深度为MN，即所有节点都走一遍）

0  字
评论
  • 按正序
  • 按倒序
  • 按热度
Powered by Waline v3.1.3
一人の境 Copyright © 2019-未知 holic-x
Copyright © 2025 holic-x