题目详情
剑指 Offer 38. 字符串的排列
输入一个字符串，打印出该字符串中字符的所有排列。
你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
示例:
1
2
| 输入：s = "abc"
输出：["abc","acb","bac","bca","cab","cba"]
|
限制：
我的解题思路
我的目标是在能过的基础上，尽可能好。
初看这道题，虽然是中等难度，但我觉得还是不是特别难。细看这道题，我想起大学老师用Python讲算法时讲的子集的题。当时用了二进制的思想，但不能用在这道题里。
在开始想过用for来交换进行排列，但太难了。
后来，我突然想到了用整体和局部视角来看，可将排列分成两个部分，对这两个部分进行排列。
再后来，我认为，每一个排列都是将一个元素放在上一个排列的左边和右边。如：元素c，上一个排列ab，那么将有排列cab和abc。
那么根据思路写出如下代码。
![解题1]()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
HashSet<String> set = new HashSet<String>();
public String[] permutation(String s) {
slove(new StringBuffer(""), new StringBuffer(s));
return set.toArray(new String[set.size()]);
}
public void slove(StringBuffer e,StringBuffer s){
if(s.length() == 1){
String t1 = new String((new StringBuffer(e)).insert(0,s));
set.add(t1);
return;
}
char t;
StringBuffer ss;
for(int i = 0 ;i<s.length();i++){
t = s.charAt(i);
ss = new StringBuffer(s);
ss.deleteCharAt(i);
slove((new StringBuffer(e)).insert(0,t),ss);
}
}
}
|
通过对其他题解进行分析，改为如下。
![解题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
| class Solution {
HashSet<String> set = new HashSet<String>();
public String[] permutation(String s) {
slove("", new StringBuffer(s));
return set.toArray(new String[set.size()]);
}
public void slove(String e,StringBuffer s){
if(s.length() == 1){
String t1 = e+s;
set.add(t1);
return;
}
char t;
StringBuffer ss;
for(int i = 0 ;i<s.length();i++){
t = s.charAt(i);
ss = new StringBuffer(s);
ss.deleteCharAt(i);
slove(e+t, ss);
}
}
}
|
虽然不知不觉写出了回溯的方法，也进行了一定的剪枝，但是当s里有相同元素时，会出现相同排列。根据我对我看了的几个题解，我认为可以对s进行排序，每次排列时找出当前元素的最大相同的子集，将其视为一个。如，baa，在进行b和a的排列时，可以将aa视为一个a。但这样会不会绕路?
我的错误或者失误
代码当然不是一下就写好的，当中也出现了许多错误。
许久没写代码了，String和StringBuffer以及其他类的方法不是特别熟悉了。
list和set的查找时间复杂度没有第一时间反应出来。
当发现超时和内存超限时，仔细分析才发现排列时把左右都排列会出双倍的重复。如abc，当a和""左右排列以及b和""左右排列后时，下一步会出现ab和ba以及ba和ab（先排右在排左），出现重复工作。如下代码9-12和21-22。
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
| class Solution {
ArrayList<String> list = new ArrayList<String>();
public String[] permutation(String s) {
slove(new StringBuffer(""), new StringBuffer(s));
return list.toArray(new String[list.size()]);
}
public void slove(StringBuffer e,StringBuffer s){
if(s.length() == 1){
String t1 = new String((new StringBuffer(e)).insert(0,s));
String t2 = new String((new StringBuffer(e)).append(s));
if(!list.contains(t1))list.add(t1);
if(!list.contains(t2))list.add(t2);
return;
}
StringBuffer t;
StringBuffer ss;
for(int i = 0 ;i<s.length();i++){
t = new StringBuffer(""+s.charAt(i));
ss = new StringBuffer(s);
ss.deleteCharAt(i);
slove((new StringBuffer(e)).insert(0,t),ss);
slove((new StringBuffer(e)).append(t),ss);
}
}
}
|
