剑指offer 38 字符串的排列

先贴出代码实现 再来说思路吧

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;

class Solution {

public ArrayList<String> Permutation(String str) {

if(str == null || str.length() == 0) {

return new ArrayList<>();
}

HashSet<String> res = new HashSet<>();

Permutation(str.toCharArray(), res, 0);

ArrayList<String> result = new ArrayList<>(res);

Collections.sort(result);

return result;
}

private void Permutation(char[] str, HashSet<String> res, int index) {

if(index == str.length - 1) {

String s = "";
for(char c : str) {

s += c;
}
res.add(s);

} else {

//递归的前半段快速的将index定位到str尾部

//这是真正全排列的地方
//假定 abcd|efg 中在abdc已经选好顺序时的全排列 就是efg的全排列
//此时index指向e 可以出现在index位置上的元素为e f g 分别交换就可以实现
for(int i = index; i < str.length; i++){
//首部字符和它后面的字符(包括自己)进行交换
swap(str, i, index);
//递归求后面的字符的排列
Permutation(str, res, index+1);
//由于前面交换了一下,所以chs的内容改变了,我们要还原回来
swap(str, i, index);

//abcdefg
//先ab交换成ba 全排列cdefg
//在还原ab 这样就可以顺利ac交换成ca 全排列cdefg
}
}
}

private void swap(char[] str, int m, int n) {

char temp = str[m];
str[m] = str[n];
str[n] = temp;
}
}


public class Main {

public static void main(String[] args) {

Solution solution = new Solution();
ArrayList<String> res = solution.Permutation("abc");

for(String s : res) {

System.out.println(s);
}
}
}

递归思路:

思路其实不难理解
首先排定第一个位置 则整体的全排列 = 排定的第一个元素 + 剩余元素的全排列
以此类推 剩余元素的全排列 = 排定的剩余元素的第一个元素 + 剩剩余元素的全排列
很明显的递归思路 但是配合代码就有点不大好理解了 网上的blog大多没有讲清楚

待排列字符串:a b c d

约定:

  1. a<->b 代表swap(a, b)
  2. a<->a+1 代表a与a后面一个元素交换 a<->a+2同理
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
29
30
31
32
33
34
Permutation(0) a<->a 排定第一个元素
Permutation(1) b<->b 排定第二个元素
Permutation(2) c<->c 排定第三个元素
Permutation(3) 只剩一个元素不用排 故排定第四个元素 存储结果: abcd
Permutation(3)相当于d<->d 现在要进行d<->d+1 故要还原d<->d
此时index=d+1越界了 说明结束 故返回
Permutation(2) 刚刚c<->c 现在要进行c<->c+1 故要还原c<->c
此时index=c+1 完成c<->d 字符串序列变为addx
Permutation(3) 只剩一个元素不用排 故排定第四个元素 存储结果: abdc
Permutation(2) 刚刚c<->c+1 现在要进行c<->c+2 故要还原c<->c+1
此时index=c+2 越界 说明结束 返回
Permutation(1) 刚b<->b 现在要进行b<->b+1 故要还原b<->b
此时index=b+1 完成b<->b+1 字符串序列变为acxx
Permutation(2) b<->b
Permutation(3) 只剩一个元素不用排 故排定第四个元素 存储结果: acbd
Permutation(2) 刚b<->b 现在要进行b<->b+1 故要还原b<->b
此时index=b+1 完成b<->b+1 字符串序列变为acdx
Permutation(3) 只剩一个元素不用排 故排定第四个元素 存储结果: acdb
Permutation(2) 刚刚b<->b+1 现在要进行b<->b+2 故要还原b<->b+1
此时index=b+2 越界 说明结束 返回
Permutation(1) 刚b<->b+1 现在要进行b<->b+2 故要还原b<->b+1
此时index=b+2 完成b<->b+2 字符串序列变为adxx
Permutation(2) c<->c
Permutation(3) 只剩一个元素不用排 故排定第四个元素 存储结果: adcb
Permutation(2) 刚c<->c 现在要进行c<->c+1 故要还原c<->c
此时index=c+1 完成c<->c+1 字符串序列变为adbx
Permutation(3) 只剩一个元素不用排 故排定第四个元素 存储结果: adbc
Permutation(2) 刚刚c<->c+1 现在要进行c<->c+2 故要还原c<->c+1
此时index=c+2 越界 说明结束 返回
Permutation(1) 刚b<->b+2 现在要进行b<->b+3 故要还原b<->b+2
此时index=b+3 越界 说明结束 返回
Permutation(0) 刚a<->a 现在要进行a<->a+1 故要还原a<->a
此时index=a+1 完成a<->a+1 字符串序列变为bxxx
...(写完了1以a开头的6种排列 剩下的思路类似 就不写了)
Donate here.