|
Contentment is natural wealth, luxury is artificial poverty.
知足是天赋的财富，奢侈是人为的贫穷。 输入一个字符串，打印出该字符串中字符的所有排列。
你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。 示例: 输入：s = "abc" 输出： ["abc","acb","bac","bca","cab","cba"]
限制： 字符串的排列其实就是排列组合，我们可以把它想象成为一棵n叉树（n是s的长度），然后每一个节点都要从字符串中选择一个字符，但注意不能选择重复的，比如在一个节点选择了a，那么他的子孙节点都不能再选择a了，我们来看个视频 看到这里我们很容易想到的一种解决方式就是回溯，具体可以看下《450，什么叫回溯算法，一看就会，一写就废》，之前我们总结回溯算法的时候有一个经典的模板
1private void backtrack("原始参数") {
2 //终止条件(递归必须要有终止条件)
3 if ("终止条件") {
4 //一些逻辑操作（可有可无，视情况而定）
5 return;
6 }
7
8 for (int i = "for循环开始的参数"; i < "for循环结束的参数"; i++) {
9 //一些逻辑操作（可有可无，视情况而定）
10
11 //做出选择
12
13 //递归
14 backtrack("新的参数");
15 //一些逻辑操作（可有可无，视情况而定）
16
17 //撤销选择
18 }
19}
这里只需要按照这个模板对他稍作修改即可，代码如下
1public String[] permutation(String s) {
2 Set<String> res = new HashSet<>();
3 backtrack(s.toCharArray(), "", new boolean[s.length()], res);
4 return res.toArray(new String[res.size()]);
5}
6
7private void backtrack(char[] chars, String temp, boolean[] visited, Set<String> res) {
8 //边界条件判断，当选择的字符长度等于原字符串长度的时候，说明原字符串的字符都已经
9 //选完了
10 if (temp.length() == chars.length) {
11 res.add(temp);
12 return;
13 }
14 //每一个节点我们都要从头开始选
15 for (int i = 0; i < chars.length; i++) {
16 //已经选择过的就不能再选了
17 if (visited[i])
18 continue;
19 //表示选择当前字符
20 visited[i] = true;
21 //把当前字符选择后，到树的下一层继续选
22 backtrack(chars, temp + chars[i], visited, res);
23 //递归往回走的时候要撤销选择
24 visited[i] = false;
25 }
26}
这里字符串中可能有重复的字符，所以结果中也会出现重复的数据，但上面使用了Set集合去重，保证了最终的排列不会出现重复的。其实还有一种方式就是先对字符串中的字符（先转化为字符数组）进行排序，然后在计算，这个就是常见的有重复数字的全排列，后续会在讲。
|
