描述
给出一个不含重复数字的排列，求这些数字的所有排列按字典序排序后该排列的编号。其中，编号从1开始。
样例
"abc" 为 "cba" 的置换。
"aabc" 不是 "abcc" 的置换。
代码
- O(n)
public class Solution {
/**
* @param A a string
* @param B a string
* @return a boolean
*/
public boolean stringPermutation(String A, String B) {
int[] cnt = new int[1000];
for (int i = 0; i < A.length(); ++i) {
cnt[(int)A.charAt(i)] += 1;
}
for (int i = 0; i < B.length(); ++i) {
cnt[(int)B.charAt(i)] -= 1;
}
for (int i = 0; i < 1000; ++i) {
if (cnt[i] != 0) {
return false;
}
}
return true;
}
}
- O(nlogn)
public class Solution {
/**
* @param A a string
* @param B a string
* @return a boolean
*/
public boolean Permutation(String A, String B) {
if (A.length() != B.length()) {
return false;
}
char[] listA = A.toCharArray();
char[] listB = B.toCharArray();
Arrays.sort(listA); // O(nlogn)
Arrays.sort(listB);
for (int i = 0; i < listA.length; i++) {
if (listA[i] != listB[i]) {
return false;
}
}
return true;
}
}
