题目说明
输入一个字符串，打印出该字符串中字符的所有排列。
示例:
1
2
| 输入：s = "abc"
输出：["abc","acb","bac","bca","cab","cba"]
|
解题思路
2.1
将abc分组，[["abc","acb"],["bac","bca"],["cab","cba"]]，第一组可以看作是将a固定，b和c进行排列，第二组可以看做是将b固定，a和c进行排列，同样第三组c固定，a和b进行排列。所以f(3) = 3*f(2)，f(n) = n*f(n-1)。那么可以用递归来实现，对字符串进行遍历，每次遍历需要将当前字符固定，然后递归剩下的字符串进行排列组合，直到递归长度为1。因为要实现排列组合，所以想到数组交换是最高效的，将每次遍历的字符和首字符交换，然后对剩下的字符进行递归，递归结束后交换回来再返回上一层。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| public String[] permutation(String s) {
char[] chars = s.toCharArray();
List<String> result = new ArrayList<>();
dfs(result, chars, 0, chars.length - 1);
return result.toArray(new String[0]);
}
private void dfs(List<String> result, char[] chars, int start, int end) {
if (start == end) {
result.add(String.valueOf(chars));
return;
}
for (int i = start; i <= end; i++) {
swap(chars, i, start);
dfs(result, chars, start + 1, end);
swap(chars, i, start);
}
}
|
2.2
当前算法还存在一个问题，如果字符串里有重复，比如aab，最终将会得到["aab","aba","aab","aba","baa","baa"]，可见结果集里出现了重复。 这个问题在于当遍历字符串的时候，
当遍历到第二个的时候，a和a交换最终得到的排列是一样的，还有baa也是一样，递归aa的时候交换就没有意义了。解决这个问题就是在每次交换字符之前先做检查，如果之前出现过，说明当下交换会产生重复。
改进后代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
private void dfs(List<String> result, char[] chars, int start, int end) {
if (start == end) {
result.add(String.valueOf(chars));
return;
}
Set<Character> set = new HashSet<>();
for (int i = start; i <= end; i++) {
if (set.contains(chars[i])) {
continue;
}
set.add(chars[i]);
swap(chars, i, start);
dfs(result, chars, start + 1, end);
swap(chars, i, start);
}
}
|
链接
剑指offer面试题38. 字符串的排列