套路

• 解决全排列问题可以用到回溯
• 全排列问题往往可以用交换两位置元素的方法，完成后续步骤后，需要回溯时再交换回原来的样子

注意点

• 暂无

目录

• 字符串的排列
• 矩阵中的路径

字符串的排列

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
输入描述:
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

public ArrayList<String> Permutation(String str) {
    ArrayList<String> res = new ArrayList<>();
    if (str == null) {
        return res;
    }
    helper(res, str.toCharArray(), 0);
    Collections.sort(res);
    return res;
}
// 回溯, i 用来固定字符串第i个索引的字母
private void helper(ArrayList<String> res, char[] arr, int i) {
    if (i == arr.length - 1) {
        if (!res.contains(String.valueOf(arr))) {
            res.add(String.valueOf(arr));
        }
        return;
    }
    // 将所有字母交换到第 i 个索引并固定
    for (int j = i; j < arr.length; j++) {
        swap(arr, i, j);
        // 对下一个索引进行递归
        helper(res, arr, i + 1);
        swap(arr, i, j);
    }
}

private void swap(char[] arr, int i, int j) {
    char temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

矩阵中的路径

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 例如 a b c e s f c s a d e e 矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。

public boolean hasPath(char[] matrix, int rows, int cols, char[] str) {
    if (matrix == null) return false;
    if (str == null) return true;
    int[] flag = new int[matrix.length];
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (helper(matrix, rows, cols, str, flag, 0, i, j)) return true;
        }
    }
    return false;
}

private boolean helper(char[] matrix, int rows, int cols, char[] str,
                       int[] flag, int index, int i, int j) {
    int k = i * cols + j;
    if (i < 0 || i >= rows || j < 0 || j >= cols || index >= str.length
        || flag[k] == 1 || str[index] != matrix[k]) return false;
    if (index == str.length - 1) return true;
    flag[k] = 1;
    boolean path = helper(matrix, rows, cols, str, flag, index + 1, i + 1, j)
                || helper(matrix, rows, cols, str, flag, index + 1, i - 1, j)
                || helper(matrix, rows, cols, str, flag, index + 1, i, j - 1)
                || helper(matrix, rows, cols, str, flag, index + 1, i, j + 1);
    flag[k] = 0;
    return path;
}