Given two strings, write a method to decide if one is a permutation of the other.
Hint
- There is one solution that is O(N logN) time. Another solution uses some space, but is O(N) time.
- Could a hash table be useful?
- Two strings that are permutations should have the same characters, but in different orders. Can you make the orders the same?
Solution
看到时间复杂度O(N logN)自然就想到可以先对字符串内的字符进行排序，然后直接比较两者的值即可。笔者在此偷个懒用了Arrays内置的排序，自己实现的话用归并或者快排皆可。额外提一下在查看JDK源码的过程中发现Arrays内置排序采用了改进后的快排DualPivotQuicksort，有兴趣的同学可以参考这篇博文 https://rerun.me/2013/06/13/quicksorting-3-way-and-dual-pivot/
public boolean isPermutation(String s1, String s2) {
if (s1 == null || s2 == null) return false;
return sort(s1).equals(sort(s2));
}
private String sort(String str) {
char[] arr = str.toCharArray();
Arrays.sort(arr);
return new String(arr);
}
另一种解法和1.1中类似，可以定义一个长度为ASCII 128的int数组，数组内存放各个字符的出现次数，遍历第一个字符串时，将字符对应位置的值加1，然后遍历第二个字符串时将该值减1，若此时出现负值，说明两边字符不一致，直接返回false即可。
public boolean isPermutation(String s1, String s2) {
if (s1 == null || s2 == null || s1.length() != s2.length()) return false;
int[] counts = new int[128];
for (char ch : s1.toCharArray()) {
counts[ch]++;
}
for (char ch : s2.toCharArray()) {
counts[ch]--;
if (counts[ch] < 0) return false;
}
return true;
}
