输入一个无重复字符的字符串s,打印出该字符串中字符的所有排列,请使用回溯法求解该问题给定s=”bcd”,请给出算法求解的结果
时间: 2024-03-19 07:45:59 浏览: 87
CC++全排列..1--n的全排列以及字符串的全排列
好的,这是一个比较经典的回溯算法问题。
算法的思路是:
1. 将字符串s转化为字符数组arr,方便操作;
2. 定义一个boolean类型的数组used,用来标识字符是否已经被使用过;
3. 定义一个StringBuilder类型的变量path,用来存储当前排列的字符序列;
4. 定义一个ArrayList类型的变量res,用来存储所有的排列结果;
5. 定义一个递归函数backtrack,该函数的参数包括:arr、used、path、res、depth,其中depth表示当前排列的深度;
6. 在backtrack函数中,如果depth等于arr的长度,则将当前排列结果加入到res中;
7. 否则,遍历arr数组,如果字符没有被使用过,则将其添加到path中,将used数组对应位置标记为true,然后递归调用backtrack函数;
8. 在递归返回后,需要将path中最后一个字符删除,并将used数组对应位置标记为false,以便进行下一次排列。
以下是具体的Java代码实现:
```java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Permutation {
public static List<String> permutation(String s) {
char[] arr = s.toCharArray();
boolean[] used = new boolean[arr.length];
StringBuilder path = new StringBuilder();
List<String> res = new ArrayList<>();
backtrack(arr, used, path, res, 0);
return res;
}
private static void backtrack(char[] arr, boolean[] used, StringBuilder path, List<String> res, int depth) {
if (depth == arr.length) {
res.add(path.toString());
return;
}
for (int i = 0; i < arr.length; i++) {
if (!used[i]) {
path.append(arr[i]);
used[i] = true;
backtrack(arr, used, path, res, depth + 1);
path.deleteCharAt(path.length() - 1);
used[i] = false;
}
}
}
public static void main(String[] args) {
String s = "bcd";
List<String> res = permutation(s);
for (String str : res) {
System.out.println(str);
}
}
}
```
输出结果为:
bcd
bdc
cbd
cdb
dbc
dcb
这就是字符串s的所有排列结果。
阅读全文