套路
- 解决全排列问题可以用到回溯
- 全排列问题往往可以用交换两位置元素的方法，完成后续步骤后，需要回溯时再交换回原来的样子
注意点
- 暂无
目录
- 字符串的排列
- 矩阵中的路径
字符串的排列
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串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;
}
