找出2个字符串是O(1)空间和O(n)时间的字谜

Question

你可以发现,如果两个字符串是O(nlogn)时间排序两个字符串后字谜,但是有没有可能找到它在O(n)的时间和O(1)空间.

Answer 1

这里绝对没有专家......

但是为什么不仔细检查每个字符串并简单计算每个字母出现的次数.

如果适当实施,这不应超过O(n)时间.

Answer 2

生成素数数组[26]每个素数代表一个字符,然后当你遍历字符串时,多个每个字符的素数,如果相等,则为anagrams,否则不是.它需要O(n)和恒定的空间

Answer 3

有几种解决方法。

方法1-使用自定义哈希码函数
我们可以使用hashCode函数，例如：

static int[] primes = {3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103};
static String alphabet = "abcdefghijklmnopqrstuvwxyz";


public static int hashCode(String s){
    int sum = 0;

    for(char c: s.toCharArray()){
      sum += primes[c-97];
    }
    return sum;
}

生成两个字符串的哈希，如果hashCode相等，则字符串为字谜。该方法类似于Jin提到的解决方案，因为它以某种方式为字符串生成hashCode。
时间复杂度-O（n）

方法2-使用字符和整数的哈希图将
2个字符串视为2个字符数组。遍历第一个数组，将字符添加到char的hashmap中并计数，找到字符时增加计数。同样遍历第二个数组，减少哈希图中的计数器，或者，如果找不到字符，则它们不是字谜。最后，当map的所有字符都计数为0时，又有2个字符串是字谜。

方法3-使用计数数组（我的最爱）

boolean are_anagrams(string1, string2){
 
    let counts = new int[26];
 
    for each char c in lower_case(string1)
        counts[(int)c]++
 
    for each char c in lower_case(string2)
        counts[(int)c]--
 
    for each int count in counts
        if count != 0
            return false
 
    return true
}

您可以在此处获取所有代码。