最近有人要求我设计一个算法，检查两个字符串是否是彼此的字谜。我的目标是最小化空间和时间复杂度，因此我想出了这个算法：
- 创建一个包含26个元素的数组，每个元素初始化为零。
- 遍历第一个字符串，对于每个字符，增加对应该字符的数组元素。
- 遍历第二个字符串，对于每个字符，减少对应该字符的数组元素。
- 扫描整个数组。如果所有元素都是0，则这两个字符串是字谜。
然而，这个算法的时间复杂度是O(n)，我无法想出更低复杂度的算法。有人知道吗？
具有最小复杂度的变位词算法
8
- garima
1
1我不是这方面的专家，但像这样的情况下O(n)已经相当高效了，不是吗？我唯一看到的缺陷是你将很难处理"über"和"rübe"，因为你受限于拉丁字符（但如果这是一个前提条件，那就没问题）。 - DarkDust
5个回答
16
你的算法是渐进最优的。无法以比 Ω(n) 更快的时间解决这个问题。为了证明这一点，假设存在一种算法A可以在 o(n) 时间内解决该问题（注意这里是小写字母o）。然后对于任何1 > ε > 0, 都有一些n，对于大小至少为 n 的任何输入，算法必须在不超过 εn 步内终止。设 ε = 1/3，并考虑到对于此 ε 的前述 n 的任何长度至少为 n 的算法输入。由于算法只能查看两个字符串中的最多 1/3 字符，那么必须存在两个不同的函数输入，一个是变位词对，另一个则不是，并且算法查看每个输入的相同字符子集。函数将不得不在每种情况下产生相同的输出，因此在至少一个输入上是错误的。我们达成了矛盾，因此不存在这样的算法。
- templatetypedef
3
通过提前退出，您可以可能提高平均性能。当扫描第二个字符串时，如果在递减之前count[char]为0，则没有变位词，您可以停止扫描。
此外，如果字符串长度小于26个字符，则在最后一步中仅检查第一个字符串中的零值字符。
这不会改变大O，但它可以将您的平均运行时间更改为低于建议解决方案的2N + 26，具体取决于您的数据。
- AShelly
2
让我们来看一个问题： 给定两个字符串s和t，编写一个函数来确定t是否是s的字谜。
例如，s =“anagram”，t =“nagaram”，返回true。 s =“rat”，t =“car”，返回false。
方法1（使用哈希表）：
public class Method1 {
public static void main(String[] args) {
String a = "protijayi";
String b = "jayiproti";
System.out.println(isAnagram(a, b ));// output => true
}
private static boolean isAnagram(String a, String b) {
Map<Character ,Integer> map = new HashMap<>();
for( char c : a.toCharArray()) {
map.put(c, map.getOrDefault(c, 0 ) + 1 );
}
for(char c : b.toCharArray()) {
int count = map.getOrDefault(c, 0);
if(count == 0 ) {return false ; }
else {map.put(c, count - 1 ) ; }
}
return true;
}
}
方法2：
public class Method2 {
public static void main(String[] args) {
String a = "protijayi";
String b = "jayiproti";
System.out.println(isAnagram(a, b));// output=> true
}
private static boolean isAnagram(String a, String b) {
int[] alphabet = new int[26];
for(int i = 0 ; i < a.length() ;i++) {
alphabet[a.charAt(i) - 'a']++ ;
}
for (int i = 0; i < b.length(); i++) {
alphabet[b.charAt(i) - 'a']-- ;
}
for( int w : alphabet ) {
if(w != 0 ) {return false;}
}
return true;
}
}
方法三：
public class Method3 {
public static void main(String[] args) {
String a = "protijayi";
String b = "jayiproti";
System.out.println(isAnagram(a, b ));// output => true
}
private static boolean isAnagram(String a, String b) {
char[] ca = a.toCharArray() ;
char[] cb = b.toCharArray();
Arrays.sort( ca );
Arrays.sort( cb );
return Arrays.equals(ca , cb );
}
}
方法四：
public class Method4 {
public static void main(String[] args) {
String a = "protijayi";
String b = "jayiproti";
//String c = "gini";
System.out.println(isAnagram(a, b ));// output => true
}
private static boolean isAnagram(String a, String b) {
Map<Integer, Integer> map = new HashMap<>();
a.codePoints().forEach(code -> map.put(code, map.getOrDefault(code, 0) + 1));
b.codePoints().forEach(code -> map.put(code, map.getOrDefault(code, 0) - 1));
//System.out.println(map.values());
for(int count : map.values()) {
if (count<0) return false;
}
return true;
}
}
- Soudipta Dutta
1
1如果您能增加每个的复杂性，那就太好了。 - Samay
1
为了确保字符串是变位词，您需要比较整个字符串 - 那么这怎么可能比O（n）更快呢？
- MacGucky
4
不，使用一个数组来存储这两个字符串似乎已经需要了最少的空间。 - MacGucky
@Garima，你的空间复杂度为O(1)，在渐进意义下不可能更好了。从绝对空间量的角度来看，你可以通过使用O(n log n)排序算法对每个字符串进行排序，然后比较结果来减少空间（代价是增加渐进运行时间复杂度）。请注意，你当前的方法本质上是对字符串进行计数排序。 - jamesdlin
@jamesdlin：空间复杂度实际上是**O(log n)**，因为计数数组的类型必须足够大，以处理
n个重复项。 - chqrlie-2
int anagram (char a[], char b[]) {
char chars[26];
int ana = 0;
int i =0;
for (i=0; i<26;i++)
chars[i] = 0;
if (strlen(a) != strlen(b))
return -1;
i = 0;
while ((a[i] != '\0') || (b[i] != '\0')) {
chars[a[i] - 'a']++;
chars[b[i] - 'a']--;
i++;
}
for (i=0; i<26;i++)
ana += chars[i];
return ana;
}
void main() {
char *a = "chimmy\0";
char *b = "yimmch\0";
printf ("Anagram result is %d.\n", anagram(a,b));
}
- asim kadav
4
如果任何一个字符串包含了
a..z 之外的字符，或者小写字母在执行字符集中不是连续的（ASCII 可以，但 EBCDIC 不行），则会出现未定义行为。 - chqrlie测试
while ((a[i] != '\0') || (b[i] != '\0')) 是多余且不正确的。您已经检查了 a 和 b 具有相同的长度，如果 a[i] 是 '\0'，即使 b[i] 不是，索引 chars[a[i] - 'a'] 也是不正确的。 - chqrlie最后一个循环没有验证所有字母是否都有零计数...实际上，数组元素的总和始终为“0”。 - chqrlie
char类型对于chars数组来说太小了：一个由256个a组成的字符串似乎与一个由256个b组成的字符串是一样的。 - chqrlie网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接