Check Permutation: Given two strings,write a method to decide if one is a permutation of the
other.
例子：
1
2
|
String a = "bbacacege";
String b = "aacbcbeeg";
|
基本判断
如果两个a.length != b.length，那么return false
排序比较
对两个字符串进行排序，然后比较是否相等
1
2
3
4
5
6
7
8
9
10
11
12
13
|
public boolean isPermuation(String a, String b) {
if (a.length() != b.length()) {
return false;
}
String sortedA = quickSort(a);
String sortedB = quickSort(b);
for(int i = 0; i < a.length(); i++) {
if (sortedA.charAt(i) != sortedB.charAt(i)) {
return false;
}
}
return true;
}
|
时间复杂度：O(2 * nlogn) + O(n) => O(nlogn)
空间复杂度：O(2 * n) => O(n)
字符计数
如果b是a的permutation，那么b里的各个字符的出现的次数肯定和a一样。如果字符集比较小的话，可以用一个int[]来做记录
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
public boolean isPermutation(String a, String b) {
if (a.length() != b.length()) {
return false;
}
int[] charCountA = new int[128];
for(int i = 0; i < a.length(); i++) {
int pos = a.charAt(i);
charCountA[pos]++;
}
int[] charCountB = new int[128];
for(int i = 0; i < b.length(); i++) {
int pos = b.charAt(i);
charCountB[pos]++;
}
for(int i = 0; i < charCountA.length(); i++) {
if (charCountA[i] != charCountB[i]) {
return false;
}
}
return true;
}
|
时间复杂度：遍历了3次，所以是O(3 * n) => O(n)
空间复杂度：两个数组，所以是O(2 * c) > O(c)，c=字符集大小
字符计数改进1
可以在遍历b字符串的时候不额外记录字符出现次数，而是直接减掉，最后看是不是为0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
public boolean isPermutation(String a, String b) {
if (a.length != b.length) {
return false;
}
int[] charCount = new int[128];
for(int i = 0; i < a.length; i++) {
int pos = a.charAt(i);
charCount[pos]++;
}
for(int i = 0; i < b.length; i++) {
int pos = b.charAt(i);
charCount[pos]--;
}
for(int i = 0; i < charCount.length; i++) {
if (charCount[i] != 0) {
return false;
}
}
return true;
}
|
时间复杂度：同样是O(n)
空间复杂度：少了一个数组，但依然是O(c)
字符计数改进2*
如果a和b的长度一样，但是b不是a的permutation，那么b肯定有一个字符计数比a少，而另一个字符计数比a多，这两个情况是同时出现的，我们只需要看是否b存在一个字符计数比a多。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
public boolean isPermutation(String a, String b) {
if (a.length != b.length) {
return false;
}
int[] charCount = new int[128];
for(int i = 0; i < a.length; i++) {
int pos = a.charAt(i);
charCount[pos]++;
}
for(int i = 0; i < b.length; i++) {
int pos = b.charAt(i);
charCount[pos]--;
if (charCount[pos] < 0) {
// b比a多了一个字符
return false;
}
}
return true;
}
|
字符计数改进3
如果字符集比较大，那么我们可以HashMap来做字符计数
评论