hashfunction() 的逻辑应该是什么来检查两个字符串是否是字谜？

Question

我想编写一个函数，将字符串作为参数，returns 是与该字符串对应的数字。

Integer hashfunction(String a)
{    
    //logic    
}

其实我解决的问题是这样的:

给定一个字符串数组，return 所有字符串组都是变位词。用表示原始列表中索引的整数列表表示一个组。

Input : cat dog god tca

Output : [[1, 4], [2, 3]]

这是我的实现：-

public class Solution {
    Integer hashfunction(String a)
    {
        int i=0;int ans=0;
        for(i=0;i<a.length();i++)
        {
            ans+=(int)(a.charAt(i));//Adding all ASCII values    
        }

        return new Integer(ans);
    }
    **Obviously this approach is incorrect**
    public ArrayList<ArrayList<Integer>> anagrams(final List<String> a) {
        int i=0;
        HashMap<String,Integer> hashtable=new HashMap<String,Integer>();
        ArrayList<Integer> mylist=new ArrayList<Integer>();
        ArrayList<ArrayList<Integer>> answer=new  ArrayList<ArrayList<Integer>>(); 
        if(a.size()==1)
        {
            mylist.add(new Integer(1));
            answer.add(mylist);
            return answer;
        }

        int j=1;
        for(i=0;i<a.size()-1;i++)
        {   

            hashtable.put(a.get(i),hashfunction(a.get(i)));
            for(j=i+1;j<a.size();j++)
            {

                if(hashtable.containsValue(hashfunction(a.get(j))))
                {
                    mylist.add(new Integer(i+1));
                    mylist.add(new Integer(j+1));
                    answer.add(mylist);
                    mylist.clear();


                }
            }
        }
        return answer;
    }
}

Answer 1

对于由相同字符组成的所有字符串，您需要一个相同的数字。

String.hashCode方法return是一个数字，对于所有由相同字符以相同顺序组成的字符串都是相同的[=13] =]

如果您可以一致地对所有单词进行排序（例如：按字母顺序排列），那么 String.hashCode 将 return 所有字谜的编号相同。

return String.valueOf(Arrays.sort(inputString.toCharArray())).hashCode();

注意：这将适用于所有的字谜词（没有漏报），但它可能不适用于所有不是字谜词的词（可能是误报）。这对于短词来说是极不可能的，但是一旦你遇到了数百个字符长的词，你就会开始遇到不止一组具有相同哈希码的变位词。

另请注意：这为您提供了问题（问题的标题）的答案，但对于您正在解决的问题来说还不够。您需要弄清楚如何将此数字与原始列表中的索引相关联。

Answer 2

哦，天哪……这里有很多东西可以解释。区分大小写、区域设置、字符 allowed/blacklisted... 将有很多方法来回答一般问题。所以，首先，让我提出一些假设：

不区分大小写。（"Rat" 是 "Tar" 的变位词，即使是大写字母。）
就字母表而言，语言环境是美式英语。（从 A 到 Z 的 26 个字母。将此与具有 28 个 IIRC 的西班牙语进行比较，其中 'll' 被视为单个字母，并且可能考虑用于西班牙语变位词！）
Whitespace 在我们的字谜定义中被忽略了。（"arthas menethil" 是 "trash in a helmet" 的变位词，尽管白色 space 的数量不同。）
一个空字符串(null, 0-length, all white-space)有一个"hash"（我更喜欢术语"digest"，但名字就是名字） 1.

如果您不喜欢这些假设中的任何一个，您可以根据需要进行修改。当然，这会导致以下算法略有不同，但它们是一套很好的指导方针，可以使通用算法相对容易理解，如果您愿意，也可以重构。

如果两个字符串完全由同一组字符组成并且每个包含的字符的数量相同，则这两个字符串是变位词。 Java 中有很多可用的工具，使这项任务相当简单。我们有 String 方法、Lists、Comparators、盒装原语和现有的 hashCode 方法……好吧，所有这些。我们将使用它们来制作我们的 "hash" 方法。

private static int hashString(String s) {
    if (s == null) return 0; // An empty/null string will return 0.

    List<Character> charList = new ArrayList<>(); 
    String lowercase = s.toLowerCase(); // This gets us around case sensitivity

    for (int i = 0; i < lowercase.length(); i++) {
        Character c = Character.valueOf(lowercase.charAt(i));
        if (Character.isWhitespace(c)) continue; // spaces don't count
        charList.add(c); // Note the character for future processing...
    }

    // Now we have a list of Characters... Sort it!
    Collections.sort(charList);
    return charList.hashCode(); // See contract of java.util.List#haschCode
}

瞧！你有一个方法可以消化一个字符串并生成一个代表它的整数，而不管其中字符的顺序。您可以以此为基础来确定两个字符串是否是彼此的变位词……但我不会。您要求生成整数的摘要函数，但请记住，在 java 中，整数只是一个 32 位值。这种方法只能产生大约 42 亿个唯一值，而您可以向它抛出的字符串远远超过 42 亿个。此方法会产生冲突并给您带来无意义的结果。如果这是一个问题，您可能需要考虑改用 BigInteger。

private static BigInteger hashString(String s) {
    BigInteger THIRTY_ONE = BigInteger.valueOf(31); // You should promote this to a class constant!

    if (s == null) return BigInteger.ONE; // An empty/null string will return 1.

    BigInteger r = BigInteger.ONE; // The value of r will be returned by this method
    List<Character> charList = new ArrayList<>(); 
    String lowercase = s.toLowerCase(); // This gets us around case sensitivity

    for (int i = 0; i < lowercase.length(); i++) {
        Character c = Character.valueOf(lowercase.charAt(i));
        if (Character.isWhitespace(c)) continue; // spaces don't count
        charList.add(c); // Note the character for future processing...
    }

    // Now we have a list of Characters... Sort it!
    Collections.sort(charList);

    // Calculate our bighash, similar to how java's List interface does.
    for (Character c : charList) {
        int charHash = c.hashCode();
        r=r.multiply(THIRTY_ONE).add(BigInteger.valueOf(charHash));
    }

    return r;
}

hashfunction() 的逻辑应该是什么来检查两个字符串是否是字谜？

What should be the logic of hashfunction() in order to check that two strings are anagrams or not?

java

hash

hashmap

anagram