具有最小复杂度的 Anagram 算法

Question

最近，我被要求设计一种算法来检查两个字符串是否是彼此的字谜。我的目标是最小化空间和时间复杂度，因此我想出了这个算法：

1. 创建一个包含 26 个元素的数组，每个元素都初始化为零。
2. 遍历第一个字符串，对于每个字符，递增与该字符对应的数组元素。
3. 遍历第二个字符串，对于每个字符，递减该字符对应的数组元素。
4. 扫描阵列。如果所有元素均为 0，则这两个字符串是字谜词。

然而，这个算法的时间复杂度是O(n)，我无法想出一个复杂度更低的算法。有人知道其中一个吗？

Answer 1

您的算法是渐近最优的。不可能在 Ω(n) 时间内解决这个问题。为了看到这一点，假设存在一个算法 A 可以在 o(n) 时间内解决问题（注意，这里是 n 的小 o）。那么对于任意 1 > ε＞ 0，存在某个 n，使得对于大小至少为 n 的任何输入，算法必须以最多 εn 个步骤终止。设置 ε = 1/3 并考虑算法的任何输入，其长度至少为 n（对于上述 ε 的 n）。由于该算法最多可以查看两个字符串中的 1/3 个字符，因此该函数必须有两个不同的输入，一个是一对字谜词，另一个不是，这样该算法就会查看每个输入的字符的相同子集。然后，该函数必须在每种情况下产生相同的输出，因此至少有一个输入是错误的。我们遇到了矛盾，所以这样的算法一定不存在。

Answer 2

通过提前退出，您可能会提高平均绩效。在扫描第二个字符串时，如果在递减之前 count[char] 为 0，则没有字谜，可以停止扫描。

此外，如果字符串短于 26 个字符，则在最后一步中，仅检查第一个字符串中的字符是否为零。

这不会改变大 O，但它可以将您的平均运行时间更改为小于建议解决方案的 2N+26，具体取决于您的数据。

Answer 3

我们来提一个问题：
给定两个字符串 s 和 t，编写一个函数来确定 t 是否是 s 的字谜词。

例如，s =“anagram”，t =“nagaram”，返回 true。 s =“老鼠”，t =“汽车”，返回 false。

方法1（使用HashMap）：

    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;

}
}

方法3：

    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 );
}
}

方法4：

    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;
}
}

Answer 4

为了确保字符串是字谜词，您需要比较整个字符串 - 那么这怎么可能比 o(n) 更快呢？

Answer 5

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));


}