2つの文字列がアナグラムであるかどうかを確認するために、hashfunction（）のロジックはどうでしょうか？

Question

文字列をパラメータとし、その文字列に対応する数値を返す関数を記述したいと思います。次のように

Integer hashfunction(String a) 
{  
    //logic  
} 

実際に質問イム解決は次のとおりです。文字列の配列を考えると

、アナグラムある文字列のすべてのグループを返します。元のリストのインデックスを表す整数のリストでグループを表します。

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

ああ、少年...ここには解釈のために開いているかなりのものがあります。大文字と小文字の区別、ロケール、文字の許可/ブラックリスト化...一般的な質問に答える方法はたくさんあります。まず、いくつかの前提を設定しましょう。

1. 大文字と小文字は関係ありません。 （「ラット」は大文字の「タール」のアナグラムです）
2. ロケールはアルファベットの場合はアメリカ英語です。 （A-Zから26文字、これはスペイン語と28個のIIRCを持つスペイン語との比較です.1つの文字とスペイン語のアナグラムの潜在的な考慮があります）
3. アナグラムの定義では空白は無視されます。
4. 空の文字列（ヌル、長さ0、すべて空白）には "ハッシュ"（I）が付いています（この場合、空白の文字列は空白文字ではありません。

これらの前提が気に入らない場合は、必要に応じて修正することができます。もちろん、これは次のアルゴリズムが少し異なりますが、一般的なアルゴリズムを比較的理解しやすくし、必要に応じてリファクタリングするためのガイドラインです。

2つの文字列は、同じ文字セットと含まれている文字の数がすべて同じ場合、アナグラムです。Javaで利用可能な多くのツールがあり、この作業はかなり単純です。 Stringメソッド、List、Comparator、boxedプリミティブ、既存のhashCodeメソッドがあります。そして、それらを使って "ハッシュ"メソッドを作成します。

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 
} 

voila;文字列を消化してその中の文字の順序にかかわらず文字列を表す整数を生成するメソッドがあります。これは、2つの文字列が互いのアナグラムであるかどうかを判断するための基礎として使用できますが、そうではありません。あなたはIntegerを生成するダイジェスト関数を求めましたが、javaではIntegerは単なる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; 
} 

Answer 2

。

String.hashCodeメソッドは、同じ文字で構成されたすべての文字列が同じ番号の同じ番号を返します。

すべての単語を一貫してソートすることができます（アルファベット順など）場合は、String.hashCodeはすべてのアナグラムで同じ番号を返します。

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

注：これはアナグラムであるすべての単語（なし偽陰性）のために動作しますが、それはアナグラムではありませんすべての単語（おそらく偽陽性）のために動作しない場合があります。これは短い単語では起こりそうにないでしょうが、何百文字もの単語になると、同じハッシュコードを持つ複数のアナグラムが出現し始めます。

注：これはあなたに質問のタイトルへの回答を与えますが、あなたが解決している質問には十分ではありません。この番号を元のリストのインデックスに関連付ける方法を理解する必要があります。