CTCI字符串排列解决方案的这个解决方案是否正确？

Question

它似乎有效，我找不到其他人有类似的答案。这太简单了——我对此持怀疑态度。

public static boolean permutation(String s, String t) {
if (s.length() != t.length()) return false; // Permutations must be same length
int sum = 0;
for(char c : s.toCharArray())
sum += c - 'a';
for(char c : t.toCharArray())
sum -= c - 'a';
return sum == 0;
}

时间复杂度是O(n(，空间复杂度是0(1(，对吗？？

Answer 1

不，你不应该因为总和而做出决定，因为如果你尝试这个permutation("CTCI", "CCCZ")会因为相同的总和而得到true

如果你想在O(N)中使用算法，你可以检查这个

public static boolean permutation(String s, String t) {
if (s.length() != t.length())
return false;
int[] freq = new int[26];
for (int i = 0; i < s.length(); i++) {
freq[s.charAt(i) % 26]++;
freq[t.charAt(i) % 26]--;
}
for (int i = 0; i < freq.length; i++) {
if (freq[i] != 0)
return false;
}
return true;
}