算法通关18关 | 回溯模板如何解决排列和单词搜索问题

1. 排列问题

题目

LeetCode46 给定一个没有重复数字的序列，返回其所有可能的全排列，

思路

排列问题的思路同样使用与字母大小写全排列LeetCode784。

元素在使用过一次的时候，在图中第二层的时候，还会再被使用，所以能用startIndex了，使用used[i]数组来标记已经选择的元素。过程如图示。

回溯要注意横向和纵向问题，for是横向，递归是纵向

终止条件：收集元素的数组大小和nums数组的大小一样大的时候，就找到了一个全排列

代码

    /**
     * 排列问题，同样适用于字母大小写全排列
     */
     List> res = new ArrayList<>();
 
      LinkedList path = new LinkedList<>();
    boolean[] used;
 
    public  List> permure(int[] nums){
        if (nums.length == 0){
            return res;
        }
        used = new boolean[nums.length];
        psermuteHelper(nums);
        return res;
    }
 
    private  void psermuteHelper(int[] nums) {
        if (path.size() == nums.length){
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            //为true的时候代表再纵向被使用过，纵向第一条元素出来的时候，会转为false
            if (used[i]){
                continue;
            }
            used[i] = true;
            path.add(nums[i]);
            psermuteHelper(nums);
            path.removeLast();
            used[i] = false;
        }
    }

2. 单词搜索

题目

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

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

思路

从上到下，从左到右，还是横向和纵向问题，每个坐标递归调用check（i,j,k)函数，i,j表示网格坐标，k表示word的第k个坐标，如果能搜索到返回true，否则返回false，check的终止条件有两种情况

1. 如果i,j位置的字符和字符串位置k的字符不相等，则这条搜索路径返回失败。
2. 如果搜索到了字符串的结尾，则找到了网格中的一条路径，这条路径上的字符正好可以组成字符串s。

两层for循环分别纵向和横向遍历寻找第一个满足的字符，然后再递归寻找下一个

代码

    public boolean exist(char[][] board,String word){
        char[] words = word.toCharArray();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (dfs(board,words,i,j,0)) return true;
            }
        }
        return false;
    }
    boolean dfs(char[][] board, char[] word, int i, int j, int k){
        //坐标越界
        if (i >= board.length || i < 0 || j >= board[0].length || j < 0 || board[i][j] != word[k]){
            return false;
        }
        //单词长度找完的时候
        if (k == word.length - 1){
            return true;
        }
        //转化为十进制0存储在ch中，十进制0对应的ASCII码中的字符即是NULL
        board[i][j] = '\0';
        boolean res = dfs(board,word,i + 1,j, k + 1) || dfs(board,word,i - 1,j, k + 1) ||
                dfs(board,word,i ,j + 1, k + 1)|| dfs(board,word,i ,j - 1, k + 1);
        board[i][j] = word[k];
        return res;
    }