java - 2 つの単語がアナグラムかどうかを確認する方法

Question

2 つの単語が互いにアナグラムであるかどうかを示すプログラムがあります。適切に動作しない例がいくつかありますが、助けていただければ幸いです。ただし、私は 1 年目のプログラマーなので、高度でない場合はそれでよかったと思います。"schoolmaster" と "theclassroom" は互いのアナグラムですが、"theclassroom" を "theclafsroom" に変更すると、まだアナグラムであると表示されます。何が間違っていますか?

import java.util.ArrayList;
public class AnagramCheck {
    public static void main(String args[]) {
        String phrase1 = "tbeclassroom";
        phrase1 = (phrase1.toLowerCase()).trim();
        char[] phrase1Arr = phrase1.toCharArray();

        String phrase2 = "schoolmaster";
        phrase2 = (phrase2.toLowerCase()).trim();
        ArrayList<Character> phrase2ArrList = convertStringToArraylist(phrase2);

        if (phrase1.length() != phrase2.length()) {
            System.out.print("There is no anagram present.");
        } else {
            boolean isFound = true;
            for (int i = 0; i < phrase1Arr.length; i++) {
                for (int j = 0; j < phrase2ArrList.size(); j++) {
                    if (phrase1Arr[i] == phrase2ArrList.get(j)) {
                        System.out.print("There is a common element.\n");
                        isFound =;
                        phrase2ArrList.remove(j);
                    }
                }
                if (isFound == false) {
                    System.out.print("There are no anagrams present.");
                    return;
                }
            }
            System.out.printf("%s is an anagram of %s", phrase1, phrase2);
        }
    }

    public static ArrayList<Character> convertStringToArraylist(String str) {
        ArrayList<Character> charList = new ArrayList<Character>();
        for (int i = 0; i < str.length(); i++) {
            charList.add(str.charAt(i));
        }
        return charList;
    }
}

Answer 1

同じ文字数と同じ文字を含む 2 つの単語は、互いのアナグラムです。文字を辞書順にソートし、1 つの文字列のすべての文字が他の文字列のすべての文字と同じ順序であるかどうかを判断するだけで済みます。

コード例を次に示します。ArraysAPI を調べて、ここで何が起こっているのかを理解してください。

public boolean isAnagram(String firstWord, String secondWord) {
     char[] word1 = firstWord.replaceAll("[\\s]", "").toCharArray();
     char[] word2 = secondWord.replaceAll("[\\s]", "").toCharArray();
     Arrays.sort(word1);
     Arrays.sort(word2);
     return Arrays.equals(word1, word2);
}

Answer 2

最速のアルゴリズムは、26 個の英字のそれぞれを一意の素数にマップすることです。次に、文字列の積を計算します。算術の基本定理により、2 つの文字列は積が同じである場合にのみアナグラムになります。

Answer 3

いずれかの配列をソートすると、解は O(n log n) になります。ただし、ハッシュマップを使用する場合、それは O(n) です。テスト済みで動作しています。

char[] word1 = "test".toCharArray();
char[] word2 = "tes".toCharArray();

Map<Character, Integer> lettersInWord1 = new HashMap<Character, Integer>();

for (char c : word1) {
    int count = 1;
    if (lettersInWord1.containsKey(c)) {
        count = lettersInWord1.get(c) + 1;
    }
    lettersInWord1.put(c, count);
}

for (char c : word2) {
    int count = -1;
    if (lettersInWord1.containsKey(c)) {
        count = lettersInWord1.get(c) - 1;
    }
    lettersInWord1.put(c, count);
}

for (char c : lettersInWord1.keySet()) {
    if (lettersInWord1.get(c) != 0) {
        return false;
    }
}

return true;

Answer 4

これは、並べ替え、複数のループ、またはハッシュ マップを使用しない、単純で高速な O(n) ソリューションです。最初の配列の各文字数をインクリメントし、2 番目の配列の各文字数をデクリメントします。結果の counts 配列がゼロでいっぱいの場合、文字列はアナグラムです。counts 配列のサイズを大きくすることで、他の文字を含めるように拡張できます。

class AnagramsFaster{

    private static boolean compare(String a, String b){
        char[] aArr = a.toLowerCase().toCharArray(), bArr = b.toLowerCase().toCharArray();
        if (aArr.length != bArr.length)
            return false;
        int[] counts = new int[26]; // An array to hold the number of occurrences of each character
        for (int i = 0; i < aArr.length; i++){
            counts[aArr[i]-97]++;  // Increment the count of the character at i
            counts[bArr[i]-97]--;  // Decrement the count of the character at i
        }
        // If the strings are anagrams, the counts array will be full of zeros
        for (int i = 0; i<26; i++)
            if (counts[i] != 0)
                return false;
        return true;
    }

    public static void main(String[] args){
        System.out.println(compare(args[0], args[1]));
    }
}

Answer 5

多くの人が解決策を提示してきましたが、私はいくつかの一般的なアプローチのアルゴリズムの複雑さについてお話ししたいと思います:

• 単純な「使用して文字を並べ替えるArrays.sort()」アプローチは、O(N log N).

• 基数ソートを使用するO(N)と、O(M)スペースが減ります。ここMで、 はアルファベットの個別の文字数です。(これは英語では 26 ですが、理論的には、多言語アナグラムを考慮する必要があります。)

• カウントの配列を使用した「文字のカウント」もO(N)...そしてソートされた文字列を再構築する必要がないため、基数ソートよりも高速です。スペース利用は になりますO(M)。

• 辞書、ハッシュマップ、ツリーマップ、または同等のものを使用した「文字数のカウント」は、アルファベットが巨大でない限り、配列アプローチよりも遅くなります。

• エレガントな「素数の積」アプローチは、残念ながらO(N^2)最悪の場合です。これは、十分に長い単語やフレーズの場合、素数の積がlong. つまり、 を使用する必要があり、 a に小さな定数BigIntegerを N 回掛けると. BigIntegerO(N^2)

  仮想的な大きなアルファベットの場合、倍率は大きくなります。素数の積をそのまま保持するための最悪の場合の空間使用法BigIntegerは (私が思うに)O(N*logM)です。

• 単語がアナグラムでない場合は、通常、hashcodeベースド アプローチが使用されます。O(N)ハッシュコードが等しい場合でも、適切なアナグラム テストを行う必要があります。したがって、これは完全な解決策ではありません。

Answer 6

私は C++ 開発者で、以下のコードは C++ です。それを行うための最も簡単で簡単な方法は次のとおりだと思います。

すべてのスロットを 0 に初期化して、サイズ 26 の int のベクトルを作成し、文字列の各文字をベクトル内の適切な位置に配置します。ベクトルはアルファベット順であるため、文字列の最初の文字が z の場合、myvector[26] になります。注: これは ASCII 文字を使用して実行できるため、基本的にコードは次のようになります。

string s = zadg;
for(int i =0; i < s.size(); ++i){
    myvector[s[i] - 'a'] = myvector['s[i] - 'a'] + 1;
} 

したがって、すべての要素を挿入すると、リストを 1 回だけトラバースするため、O(n) 時間がかかります。2 番目の文字列に対してまったく同じことを実行できるようになりましたが、それにも O(n) 時間がかかります。次に、各スロットのカウンターが同じかどうかを確認することで、2 つのベクトルを比較できます。もしそうなら、それはあなたが両方の文字列に同じ数の各文字を持っていたことを意味し、したがってそれらはアナグラムです. 2 つのベクトルの比較にも O(n) 時間がかかるはずです。

注: このコードは、1 単語の文字に対してのみ機能します。スペース、数字、記号がある場合は、サイズ 96 (ASCII 文字 32 ～ 127) のベクトルを作成するだけで、'a' の代わりに ' ' と言うことができます。文字の ASCII リスト。

それが役立つことを願っています。私がどこかで間違いを犯した場合は、コメントを残してください。

Answer 7

    /*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package Algorithms;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import javax.swing.JOptionPane;

/**
 *
 * @author Mokhtar
 */
public class Anagrams {

    //Write aprogram to check if two words are anagrams
    public static void main(String[] args) {
        Anagrams an=new Anagrams();
        ArrayList<String> l=new ArrayList<String>();
        String result=JOptionPane.showInputDialog("How many words to test anagrams");
        if(Integer.parseInt(result) >1)
        {    
            for(int i=0;i<Integer.parseInt(result);i++)
            {

                String word=JOptionPane.showInputDialog("Enter word #"+i);
                l.add(word);   
            }
            System.out.println(an.isanagrams(l));
        }
        else
        {
            JOptionPane.showMessageDialog(null, "Can not be tested, \nYou can test two words or more");
        }

    }

    private static String sortString( String w )
    {
        char[] ch = w.toCharArray();
        Arrays.sort(ch);
        return new String(ch);
    }

    public boolean isanagrams(ArrayList<String> l)
    {
        boolean isanagrams=true; 
        ArrayList<String> anagrams = null;
        HashMap<String, ArrayList<String>> map =  new HashMap<String, ArrayList<String>>();
        for(int i=0;i<l.size();i++)
            {
        String word = l.get(i);
        String sortedWord = sortString(word);
            anagrams = map.get( sortedWord );
        if( anagrams == null ) anagrams = new ArrayList<String>();
        anagrams.add(word);
        map.put(sortedWord, anagrams);
            }

            for(int h=0;h<l.size();h++)
            {
                if(!anagrams.contains(l.get(h)))
                {
                    isanagrams=false;
                    break;
                }
            }

            return isanagrams;
        //}
        }

}

Answer 8

コメントをしていただきありがとうございます。コメントを作成しているときに、間違ったロジックがあることがわかりました。ロジックを修正し、コードごとにコメントを追加しました。

// Time complexity: O(N) where N is number of character in String
// Required space :constant space.
// will work for string that contains ASCII chars

private static boolean isAnagram(String s1, String s2) {

    // if length of both string's are not equal then they are not anagram of each other 
    if(s1.length() != s2.length())return false;

    // array to store the presence of a character with number of occurrences.   
    int []seen = new int[256];

    // initialize the array with zero. Do not need to initialize specifically  since by default element will initialized by 0.
    // Added this is just increase the readability of the code. 
    Arrays.fill(seen, 0);

    // convert each string to lower case if you want to make ABC and aBC as anagram, other wise no need to change the case.  
    s1 = s1.toLowerCase();
    s2 = s2.toLowerCase();

    //  iterate through the first string and count the occurrences of each character
    for(int i =0; i < s1.length(); i++){
        seen[s1.charAt(i)] = seen[s1.charAt(i)] +1;
    }

    // iterate through second string and if any char has 0 occurrence then return false, it mean some char in s2 is there that is not present in s1.
    // other wise reduce the occurrences by one every time .
    for(int i =0; i < s2.length(); i++){
        if(seen[s2.charAt(i)] ==0)return false;
        seen[s2.charAt(i)] = seen[s2.charAt(i)]-1;
    }

    // now if both string have same occurrence of each character then the seen array must contains all element as zero. if any one has non zero element return false mean there are 
    // some character that either does not appear in one of the string or/and mismatch in occurrences 
    for(int i = 0; i < 256; i++){
        if(seen[i] != 0)return false;
    }
    return true;
}

Answer 9

これまでのところ、提案されているすべてのソリューションcharは、コード ポイントではなく、個別のアイテムで機能します。サロゲート ペアも適切に処理するための 2 つの解決策を提案したいと思います (これらはU+10000 から U+10FFFF までの文字で、2 つの項目で構成されcharます)。

1) Java 8ストリームを利用する 1 行のO(n logn)ソリューション:CharSequence.codePoints()

static boolean areAnagrams(CharSequence a, CharSequence b) {
    return Arrays.equals(a.codePoints().sorted().toArray(),
                         b.codePoints().sorted().toArray());
}

2) 洗練されていないO(n)ソリューション(実際、アナグラムになる可能性が低い長い文字列の場合にのみ高速になります) :

static boolean areAnagrams(CharSequence a, CharSequence b) {
    int len = a.length();
    if (len != b.length())
        return false;

    // collect codepoint occurrences in "a"
    Map<Integer, Integer> ocr = new HashMap<>(64);
    a.codePoints().forEach(c -> ocr.merge(c, 1, Integer::sum));

    // for each codepoint in "b", look for matching occurrence
    for (int i = 0, c = 0; i < len; i += Character.charCount(c)) {
        int cc = ocr.getOrDefault((c = Character.codePointAt(b, i)), 0);
        if (cc == 0)                        
            return false;            
        ocr.put(c, cc - 1);
    }
    return true;
}

Answer 10

import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;
/**
 * Check if Anagram by Prime Number Logic
 * @author Pallav
 *
 */
public class Anagram {
    public static void main(String args[]) {
        System.out.println(isAnagram(args[0].toUpperCase(),
                args[1].toUpperCase()));
    }
/**
 * 
 * @param word : The String 1
 * @param anagram_word : The String 2 with which Anagram to be verified
 * @return true or false based on Anagram
 */
    public static Boolean isAnagram(String word, String anagram_word) {
        //If length is different return false
        if (word.length() != anagram_word.length()) {
            return false;
        }
        char[] words_char = word.toCharArray();//Get the Char Array of First String
        char[] anagram_word_char = anagram_word.toCharArray();//Get the Char Array of Second String
        int words_char_num = 1;//Initialize Multiplication Factor to 1
        int anagram_word_num = 1;//Initialize Multiplication Factor to 1 for String 2
        Map<Character, Integer> wordPrimeMap = wordPrimeMap();//Get the Prime numbers Mapped to each alphabets in English
        for (int i = 0; i < words_char.length; i++) {
            words_char_num *= wordPrimeMap.get(words_char[i]);//get Multiplication value for String 1
        }
        for (int i = 0; i < anagram_word_char.length; i++) {
            anagram_word_num *= wordPrimeMap.get(anagram_word_char[i]);//get Multiplication value for String 2
        }

        return anagram_word_num == words_char_num;
    }
/**
 * Get the Prime numbers Mapped to each alphabets in English
 * @return
 */
    public static Map<Character, Integer> wordPrimeMap() {
        List<Integer> primes = primes(26);
        int k = 65;
        Map<Character, Integer> map = new TreeMap<Character, Integer>();
        for (int i = 0; i < primes.size(); i++) {
            Character character = (char) k;
            map.put(character, primes.get(i));
            k++;
        }
        // System.out.println(map);
        return map;
    }
/**
 * get first N prime Numbers where Number is greater than 2
 * @param N : Number of Prime Numbers
 * @return
 */
    public static List<Integer> primes(Integer N) {
        List<Integer> primes = new ArrayList<Integer>();
        primes.add(2);
        primes.add(3);

        int n = 5;
        int k = 0;
        do {
            boolean is_prime = true;
            for (int i = 2; i <= Math.sqrt(n); i++) {
                if (n % i == 0) {
                    is_prime = false;
                    break;
                }
            }

            if (is_prime == true) {
                primes.add(n);

            }
            n++;
            // System.out.println(k);
        } while (primes.size() < N);

        // }

        return primes;
    }

}

Answer 11

アナグラムを見つけるために「ハッシュコード」アプローチを使用した人は誰もいないことがわかりました。私のアプローチは、上記のアプローチとほとんど変わらないことがわかったので、共有することを考えました。O（n）で機能するアナグラムを見つけるために、以下のコードを書きました。

/**
 * This class performs the logic of finding anagrams
 * @author ripudam
 *
 */
public class AnagramTest {

    public static boolean isAnagram(final String word1, final String word2) {

            if (word1 == null || word2 == null || word1.length() != word2.length()) {
                 return false;
            }

            if (word1.equals(word2)) {
                return true;
            }

            final AnagramWrapper word1Obj = new AnagramWrapper(word1);
            final AnagramWrapper word2Obj = new AnagramWrapper(word2);

            if (word1Obj.equals(word2Obj)) {
                return true;
            }

            return false;
        }

        /*
         * Inner class to wrap the string received for anagram check to find the
         * hash
         */
        static class AnagramWrapper {
            String word;

            public AnagramWrapper(final String word) {
                this.word = word;
            }

            @Override
            public boolean equals(final Object obj) {

                return hashCode() == obj.hashCode();
            }

            @Override
            public int hashCode() {
                final char[] array = word.toCharArray();
                int hashcode = 0;
                for (final char c : array) {
                    hashcode = hashcode + (c * c);
                }
                return hashcode;
            }
         }
    }

Answer 12

申し訳ありませんが、ソリューションは C# にありますが、ソリューションに到達するために使用されるさまざまな要素は非常に直感的だと思います。ハイフン付きの単語には微調整が必​​要ですが、通常の単語では問題なく動作するはずです。

    internal bool isAnagram(string input1,string input2)
    {
        Dictionary<char, int> outChars = AddToDict(input2.ToLower().Replace(" ", ""));
        input1 = input1.ToLower().Replace(" ","");
        foreach(char c in input1)
        {
            if (outChars.ContainsKey(c))
            {
                if (outChars[c] > 1)
                    outChars[c] -= 1;
                else
                    outChars.Remove(c);
            }
        }
        return outChars.Count == 0;
    }

    private Dictionary<char, int> AddToDict(string input)
    {
        Dictionary<char, int> inputChars = new Dictionary<char, int>();
        foreach(char c in input)
        {
            if(inputChars.ContainsKey(c))
            {
                inputChars[c] += 1;
            }
            else
            {
                inputChars.Add(c, 1);
            }     
        }
        return inputChars;
    }

Answer 13

testString が baseString のアナグラムであるかどうかを判断するための簡単な方法。

private static boolean isAnagram(String baseString, String testString){
    //Assume that there are no empty spaces in either string.

    if(baseString.length() != testString.length()){
        System.out.println("The 2 given words cannot be anagram since their lengths are different");
        return false;
    }
    else{
        if(baseString.length() == testString.length()){
            if(baseString.equalsIgnoreCase(testString)){
                System.out.println("The 2 given words are anagram since they are identical.");
                return true;
            }
            else{
                List<Character> list = new ArrayList<>();

                for(Character ch : baseString.toLowerCase().toCharArray()){
                    list.add(ch);
                }
                System.out.println("List is : "+ list);

                for(Character ch : testString.toLowerCase().toCharArray()){
                    if(list.contains(ch)){
                        list.remove(ch);
                    }
                }

                if(list.isEmpty()){
                    System.out.println("The 2 words are anagrams");
                    return true;
                }
            }
        }
    }
    return false;
}

Answer 14

private static boolean checkAnagram(String s1, String s2) {
   if (s1 == null || s2 == null) {
       return false;
   } else if (s1.length() != s2.length()) {
       return false;
   }
   char[] a1 = s1.toCharArray();
   char[] a2 = s2.toCharArray();
   int length = s2.length();
   int s1Count = 0;
   int s2Count = 0;
   for (int i = 0; i < length; i++) {
       s1Count+=a1[i];
       s2Count+=a2[i];
   }
   return s2Count == s1Count ? true : false;
}

Answer 15

次のようなものを使用する必要があります。

    for (int i...) {
        isFound = false;
        for (int j...) {
            if (...) {
                ...
                isFound = true;
            }
        }

のデフォルト値はisFoundfalse にする必要があります。それだけ

Answer 16

完璧に動作します！ただし、O(n^2) で実行されるため、良いアプローチではありません。

boolean isAnagram(String A, String B) {
    if(A.length() != B.length())
        return false;

   A = A.toLowerCase();
   B = B.toLowerCase();

   for(int i = 0; i < A.length(); i++){
       boolean found = false;
       for(int j = 0; j < B.length(); j++){
           if(A.charAt(i) == B.charAt(j)){
               found = true;
               break;
           }
       }
       if(!found){
           return false;
       }
   }

   for(int i = 0; i < B.length(); i++){
       boolean found = false;
       for(int j = 0; j < A.length(); j++){
           if(A.charAt(j) == B.charAt(i)){
               found = true;
               break;
           }
       }
       if(!found){
           return false;
       }
   }

   int sum1 = 0, sum2 = 0;
   for(int i = 0; i < A.length(); i++){
       sum1 += (int)A.charAt(i);
       sum2 += (int)B.charAt(i);               
   }

   if(sum1 == sum2){
       return true;
   } 
   return false;
}

Answer 17

これを解決する方法 - Sai Kiran の回答に基づく..

import java.util.Scanner;

public class Anagram {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        System.out.print("Enter first word : ");
        String word1 = sc.nextLine();
        System.out.print("Enter second word : ");
        String word2 = sc.nextLine();

        sc.close();

        System.out.println("Is Anagram : " + isAnagram(word1, word2));
    }

    private static boolean isAnagram(String word1, String word2) {

        if (word1.length() != word2.length()) {
            System.err.println("Words length didn't match!");
            return false;
        }

        char ch1, ch2;
        int len = word1.length(), sumOfWord1Chars = 0, sumOfWord2Chars = 0;

        for (int i = 0; i < len; i++) {
            ch1 = word1.charAt(i);
            if (word2.indexOf(ch1) < 0) {
                System.err.println("'" + ch1 + "' not found in \"" + word2
                        + "\"");
                return false;
            }
            sumOfWord1Chars += word1.charAt(i);

            ch2 = word2.charAt(i);
            if (word1.indexOf(ch2) < 0) {
                System.err.println("'" + ch2 + "' not found in \"" + word1
                        + "\"");
                return false;
            }
            sumOfWord2Chars += word2.charAt(i);
        }

        if (sumOfWord1Chars != sumOfWord2Chars) {
            System.err
                    .println("Sum of both words didn't match, i.e., words having same characters but with different counts!");
            return false;
        }

        return true;
    }
}

Answer 18

このような単純な作業には非常に厄介なようです。

まず、

あなたのループは複雑すぎます。このようなことを試してください。

public static String lettersOnly(String word) 
{
    int length = word.length();
    StringBuilder end = new StringBuilder(length);
    char x;

    for (int i = (length - 1); i >= 0; i--) {
        x = word.charAt(i);
        if (Character.isLetter(x)) {
            end.append(x);
        }
    }
    return end.toString();

これは、それらがアナグラムであるかどうかを確認するためのはるかに単純な方法です。

すべての印刷に対して別の方法を作成することもできます。これははるかに簡単です。

そして最後に、使用するだけです

    String ltrsOnlyOne = lettersOnly(wordOne);
    String ltrsOnlyTwo = lettersOnly(wordTwo);

文字列を作成するため。