java - Javaのアナグラムアルゴリズム

Question

アナグラムアルゴリズムを作りたいのですが、このコードは動きません。私のせいはどこですか？たとえば、des と sed はアナグラムですが、出力はアナグラムではありません。一方、string メソッドを使用する必要があります。配列ではありません。:)

public static boolean isAnagram(String s1 , String s2)
{
    String delStr="";
    String newStr="";

    for(int i=0;i<s1.length();i++)
    {
        for(int j=0 ; j < s2.length() ; j++)
        {
            if(s1.charAt(i)==s2.charAt(j))
            {
                delStr=s1.substring(i,i+1);
                newStr=s2.replace(delStr,"");
            }
        }           
    }

    if(newStr.equals(""))
        return true;
    else
        return false;
}

score 31 · Accepted Answer

簡単な方法は、両方の文字列の文字を並べ替えて、それらが等しいかどうかを比較することです。

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

        // Early termination check, if strings are of unequal lengths,
        // then they cannot be anagrams
        if ( s1.length() != s2.length() ) {
            return false;
        }
        s1=s1.toLowerCase();
        s2=s2.toLowerCase();
        char[] c1 = s1.toCharArray();
        char[] c2 = s2.toCharArray();
        Arrays.sort(c1);
        Arrays.sort(c2);
        String sc1 = new String(c1);
        String sc2 = new String(c2);
        return sc1.equals(sc2);
}

個人的には、ネストされた for-loops =p よりも読みやすいと思います

これにはO(n log n)実行時の複雑nさがあり、は長い文字列の長さです。

編集:これは最適な解決策ではありません。最も効率的なアプローチについては、@aam1r の回答を参照してください (つまり、インタビューで実際に言うべきこと)。

score 30 · Accepted Answer

これは、定数スペースを使用して線形時間で実行できます。開始に役立つ疑似コードを次に示します。

// Create new hashtable/hashmap to keep track of how many times each character
// is being used
character_map -> new hash map

// Initial check. If lengths are not the same, they can't be anagrams.
if s1.length != s2.length:
    throw exception "Not anagrams"

// Add all characters from s1 to hashmap. Increment the value to keep track of
// number of occurences
foreach character c1 in s1:
    character_map[c1]++

// Iterate through all character in s2 and decrement count of each character.
foreach character c2 in s2:
    character_map[c2]--

// If they are anagrams, each character should be at "0" count at the point.
// If we come across a character that is not, it means that they are not anagrams
foreach key k, value v in character_map:
    if v != 0:
            throw exception "Not anagrams"

このコードはソートされないため、単純なループを使用して実行できます。全体の実行時間は O(n) で、全体のスペースは O(1) です。したがって、最速のソリューションです。ハッシュマップに含めることができる要素の数は一定です (つまり、アルファベットセットに項目がいくつあるかはわかっています)。

score 9 · Accepted Answer

if(s1.charAt(i)==s2.charAt(j))
        delStr=s1.substring(i,i+1);
        newStr=s2.replace(delStr,"");

このコードは、ステートメントが 1 つしかない場合でも、常にを使用する必要がある理由を示す良い例ですcurly braces。ifあなたの 2 番目の割り当ては、実際にはの外にありif-condition、常に発生します。

2 つの文字列を確認する最善の方法Anagramは、それらを文字配列に変換すること(String#toCharArray)です。次に、Arrays.sortメソッドを使用してそれらを並べ替えます。そして、それらを比較してください。

更新しました： -

メソッドを使いたいだけならString、ネストされたループは実際には必要ありません。たった1つでできます。

これがあなたの修正されたコードです： -

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

    if (s1.length() != s2.length()) {
        return false;
    }

    for(int i = 0; i < s2.length(); i++) {

            if( !s1.contains("" + s2.charAt(i))) {
                return false;
            }

            s1 = s1.replaceFirst("" + s2.charAt(i), "");
            s2 = s2.replaceFirst("" + s2.charAt(i), "");
    }
    return true;
}

score 8 · Accepted Answer

より効率的なのは、文字列を並べ替えた順序で比較することです。

public static boolean isAnagram(String s1 , String s2) {
    return s1.length() == s2.length() 
        && checkSum(s1) == checkSum(s2)
        && Arrays.equals(lettersSorted(s1), lettersSorted(s2));
}

static long checkSum(String s) {
    long sqrSum = 0;
    for(int i = 0; i < s.length(); s++) {
       char ch = s.charAt(i);
       sqrSum += ch + (1L << ch);
    }
}

static char[] lettersSorted(String s) {
    char[] chars = s.toCharArray();
    Arrays.sort(chars);
    return chars;
}

これは O(N ln N) アルゴリズムですが、文字列が通常アナグラムでない場合、平均で O(N) になります。

score 7 · Accepted Answer

あなたが何をしようとしているのかはわかりませんが、うまくいかないことは確かです (そしてで実行されO(n^2)ます。代わりにこれを試してください (これはで実行されますO(n log n)):

public static boolean isAnagram(String s1, String s2){
  if (s1.length() != s2.length()) return false;

  char[] c1 = s1.toCharArray();
  char[] c2 = s2.toCharArray();

  Arrays.sort(c1);
  Arrays.sort(c2);

  for(int i = 0; i < c1.length; i++) {
    if(c1[i] != c2[i]) return false;
  }

  return true;
}

score 3 · Accepted Answer

うまくいかない理由：

例として「des」と「sed」を使用します。

一致する最後の反復では、次のように評価されます。

if(s1.charAt(i)==s2.charAt(j))
{
    delStr=s1.substring(i,i+1);
    newStr=s2.replace(delStr,"");
}

if( "s" == "s" )

次に、if ブロックに入り、評価します。

newStr = "sed".replace("s","");

これにより、空の文字列の代わりに「ed」が返されます。

この話の教訓は、常に s2 から 1 文字少ない文字を置き換えているということです。これは決して空にはなりません。

String.replace() を使用すると、デフォルトで文字のすべてのインスタンスが置き換えられるため、とにかく悪いです。String.replace() を使用すると、「sed」は「seeeeeeed」のアナグラムと見なされます。String.replaceFirst() を使用することをお勧めします。

いずれにせよ、出発点は次の変更を行うことです。

String newStr = s2;
...
// inside if block
newStr = newStr.replaceFirst( delStr, "" );

score 3 · Accepted Answer

以下は、2 つの文字列が 2 つの文字列の 1 回の繰り返しと、256 要素配列の最後の繰り返しでアナグラムであるかどうかを判断する簡潔なコードスニペットです。このアプローチでは、マッピング配列に文字数を記録することで、文字列内の文字の並べ替えや、文字列/文字配列との間の変換を回避します。

static boolean isAnagram(String s1, String s2) {
    if (s1.length() != s2.length()) return false;
    int n = s1.length();
    int[] charMap = new int[256];
    for (int i = 0; i < n; i++) {
        char c1 = s1.charAt(i);
        charMap[c1]++;
        char c2 = s2.charAt(i);
        charMap[c2]--;
    }
    for (int i = 0; i < charMap.length; i++) {
        if (charMap[i] != 0) return false;
    }
    return true;
}

このコードは基本的に、文字に対応する配列内のインデックス位置をインクリメントおよびデクリメントします。反復の最後に配列要素のいずれかがゼロ以外の場合、インクリメントとデクリメントの量が等しくないため、文字列には異なる文字が含まれており、互いのアナグラムにすることはできません。

このアルゴリズムが 2 つの同じサイズの文字列を 1 回繰り返すとすると、ランタイムは O(n) になります。charMap は文字セットの要件に応じて常に一定であるため、スペースの複雑さは O(1) です。

score 3 · Accepted Answer

import java.util.Scanner;

public class Anagrams {

static boolean isAnagram(String a, String b) {
    a = a.toLowerCase();
    b = b.toLowerCase();
    if (a.length() != b.length()) {
        return false;
    }

    char[] chars = a.toCharArray();
    for (char c : chars) {
        int index = b.indexOf(c);
        if (index != -1) {
            b = b.substring(0, index) + b.substring(index + 1, b.length());
        } else {
            return false;
        }
    }
    return b.isEmpty();
}

public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    String a = scan.next();
    String b = scan.next();
    scan.close();
    boolean ret = isAnagram(a, b);
    System.out.println((ret) ? "Anagrams" : "Not Anagrams");

    }
}

score 1 · Accepted Answer

O(n) ソリューションで、並べ替えを一切行わず、マップを 1 つだけ使用します。また、他のソリューションで欠落している適切な null チェックを追加しました。

public boolean isAnagram(String leftString, String rightString) {
  if (leftString == null || rightString == null) {
    return false;
  } else if (leftString.length() != rightString.length()) {
    return false;
  }

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

  for(int i = 0; i < leftString.length(); i++){
    char charFromLeft = leftString.charAt(i);
    int nrOfCharsInLeft = occurrencesMap.containsKey(charFromLeft) ? occurrencesMap.get(charFromLeft) : 0;
    occurrencesMap.put(charFromLeft, ++nrOfCharsInLeft);
    char charFromRight = rightString.charAt(i);
    int nrOfCharsInRight = occurrencesMap.containsKey(charFromRight) ? occurrencesMap.get(charFromRight) : 0;
    occurrencesMap.put(charFromRight, --nrOfCharsInRight);
  }

  for(int occurrencesNr : occurrencesMap.values()){
    if(occurrencesNr != 0){
      return false;
    }
  }

  return true;
}

一般的ではない解決策ですが、少し高速です：

public boolean isAnagram(String leftString, String rightString) {
  if (leftString == null || rightString == null) {
    return false;
  } else if (leftString.length() != rightString.length()) {
    return false;
  }

  char letters[] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};
  Map<Character, Integer> occurrencesMap = new HashMap<>();
  for (char l : letters) {
    occurrencesMap.put(l, 0);
  }

  for(int i = 0; i < leftString.length(); i++){
    char charFromLeft = leftString.charAt(i);
    Integer nrOfCharsInLeft = occurrencesMap.get(charFromLeft);
    occurrencesMap.put(charFromLeft, ++nrOfCharsInLeft);
    char charFromRight = rightString.charAt(i);
    Integer nrOfCharsInRight = occurrencesMap.get(charFromRight);
    occurrencesMap.put(charFromRight, --nrOfCharsInRight);
  }

  for(Integer occurrencesNr : occurrencesMap.values()){
    if(occurrencesNr != 0){
      return false;
    }
  }

  return true;
}

score 0 · Accepted Answer

これは、HashMap の代わりに配列を使用するために私が作成した Java 実装です。これによりスペースが節約され、さらに配列は非常に高速です。

public static boolean anagram(String s, String t) { 
        if (s.length() != t.length()) return false;

        int[] arr = new int[123];
        for (char c : s.toCharArray())
            arr[c]++;
        for (char c : t.toCharArray())
            arr[c]--;
        for (int i : arr)
            if (i != 0)
                return false;
        return true;
    }

score 0 · Accepted Answer

次の解決策はO(n)複雑だと思います。誰かが違う場合はお知らせください。

import java.util.HashMap;
import java.util.Scanner;


public class Anagrams {

    static boolean isAnagram(String word1, String word2)
    {
        if(word1.length() != word2.length()) {
            return false;
        }
        int flag=0;
        HashMap<Character,Integer> table = new HashMap<Character,Integer>();
        for(int i=0; i< word1.length();i++) {
            table.put(word1.charAt(i),1);
        }

        for(int i=0; i< word2.length();i++) {
            if(table.containsKey(word2.charAt(i))) {
                continue;
            } else {
                flag=1;
                break;
            }   
        }
        return flag == 0;
    }

    public static void main(String[] args) {
        System.out.println("Enter your string");
        Scanner sc= new Scanner(System.in);
        String word1= sc.nextLine();
        String word2=sc.nextLine();

         boolean result = isAnagram(word1,word2);
         if(result) {
             System.out.println("The words are Anagrams");
         } else{
             System.out.println("The words are not Anagrams");   
         }
    }
}

score 0 · Accepted Answer

アナグラムについての就職面接のテストをしたことがあります。github アカウントにアップロードしました。Java コードは、(複数行の) テキストファイルがアナグラムポエムまたはアナグラムテキストであるかどうかをチェックします。

https://github.com/javocsoft/anagram_poem_checker

それが役に立てば幸い！

さよなら。

score 0 · Accepted Answer

実際にロジックを書き留めて、2 つの文字列がアナグラムかどうかをチェックするコードを書くのに時間がかかりました。もちろん、上記の回答の助けを借りて！XD

public static void main(String[] args) {

    Map<Character, Integer> char_map = new HashMap<Character, Integer>();
    Map<Character, Integer> empty_map = new HashMap<Character, Integer>();
    String a = "HelloP";
    String b = "HePlol";

    if (a.length() != b.length()) {
        System.out.println("false");
        System.exit(0);
    }

    for (char c : a.toLowerCase().toCharArray()) {
        empty_map.put(c, 0);
        if (char_map.containsKey(c))
            char_map.put(c, 1 + char_map.get(c));
        else
            char_map.put(c, 1);
    }

    for (char c : b.toLowerCase().toCharArray())
        if (char_map.containsKey(c))
            char_map.put(c, char_map.get(c) - 1);

    System.out.println(char_map.equals(empty_map));
}

score 0 · Accepted Answer

念のため、s1 が s2 のアナグラムであるかどうかを確認しようとしていますか? これは、s2 が s1 のアナグラムであることも意味します。したがって、s1 と s2 を並べ替えて、それらが等しいかどうかを確認します。

String string1 = "fdafdas";
String string2 = "fdwqkjl";
char[] chars = string1.toCharArray();
char[] chars2 = string2.toCharArray();
Arrays.sort(chars);
Arrays.sort(chars2);
string1 = new String(chars);
string2 = new String(chars2);
if (string1.equals(string2)) {
    //They are an anagram
}

score 0 · Accepted Answer

アナグラム部分文字列のビットベクトルアプローチを使用した高速バージョン

public boolean isAnagram(String _source1, String _source2)
{

    int flag = 0, char_index = 0, counter = 0;
    if(_source2.length() < _source1.length()){
        return false;
    }
    char[] _stringchar = _source1.toCharArray();
    char[] _tocheck = _source2.toCharArray();
    for(char character : _stringchar)
    {
        char_index = character - 'a';
        if((flag & (1 << char_index)) == 0)
            flag |= (1 << char_index);
    }

    for(char toCheckcChar : _tocheck)
    {
        char_index = toCheckcChar - 'a';

        if((flag & (1 << char_index)) > 0)
            counter++;
        else
            counter = 0;

        if(counter == _source1.length())
            return true;

    }

    return false;
}

score 0 · Accepted Answer

import java.util.Scanner;

public class JavaProgram
{
    public static void main(String[] input)
    {
        String str1, str2;
        int len, len1, len2, i, j, found=0, not_found=0;
        Scanner scan = new Scanner(System.in);

        System.out.print("Enter First String : ");
        str1 = scan.nextLine();
        System.out.print("Enter Second String : ");
        str2 = scan.nextLine();

        len1 = str1.length();
        len2 = str2.length();

        if(len1 == len2)
        {
            len = len1;
            for(i=0; i<len; i++)
            {
                found = 0;
                for(j=0; j<len; j++)
                {
                    if(str1.charAt(i) == str2.charAt(j))
                    {
                        found = 1;
                        break;
                    }
                }
                if(found == 0)
                {
                    not_found = 1;
                    break;
                }
            }
            if(not_found == 1)
            {
                System.out.print("Strings are not Anagram to Each Other..!!");
            }
            else
            {
                System.out.print("Strings are Anagram");
            }
        }
        else
        {
            System.out.print("Both Strings Must have the same number of Character to be an Anagram");
        }
    }
}

score 0 · Accepted Answer

これがあなたの観点からの私の解決策です

private static boolean isAnagram(String s1, String s2){
    int count = 0;
    boolean flag = false;

    if(s1.length() != s2.length()){
        return false;
    }
    //checks whether both word's letters are the same
    for (int i = 0; i < s1.length(); i++){
        for (int j = 0; j < s2.length(); j++){
            if(s1.charAt(i) == s2.charAt(j)){
                count++;
                break;
            }
        }
    }
    //if count equals to one of the Strings length then it is an anagram
    if(count == s2.length() ){
        flag = true;
    }
    return flag;
}

score 0 · Accepted Answer

public static boolean isAnagram(String s1, String s2) {
    boolean aux = true;
    if (s1.length() != s2.length()){
        aux = false;
    }else{ 
        for (int i = 0; i < s1.length(); i++)
            if(s2.toUpperCase().indexOf(s1.toUpperCase().substring(i, i+1)) == -1) aux = false;
    }
    return aux;
}

score 0 · Accepted Answer

単純な理由は、replace 関数が新しいStringオブジェクトを作成するためです。s2Javaでは、文字列は本質的に最終的なものであるため、実際の文字列（あなたの場合）には何もしません。したがって、cmonkey で指摘されているように、文字列 s2 から常に 1 文字を削除していますが、実際にStringは 1 文字少ない新しいオブジェクトが作成され、s2 はそのまま残ります。

あなたのケースでこれを機能させる簡単な方法は、新しい文字列オブジェクトを作成して自分自身に割り当てることです。

{
    s2=s2.replace(delString,"");
    ....
    if(s2.empty()) return true;
    return false;
}

score 0 · Accepted Answer

行 newStr=s2.replace(delStr,""); を参照してください。

ここで s2 の char を置き換えて newStr に代入するということは、s2 で何も変更していないことを意味します。このコードを以下のコードに置き換えるだけで問題なく動作します

newStr=newStr.replace(delStr,"");

score -2 · Accepted Answer

import java.util.*;
class Anagrams 
{
    public static void main(String[] args) 
    {
        System.out.println("Enter the two words");
        Scanner scan = new Scanner(System.in);
        String word1 = scan.next();
        String word2=scan.next();

        StringBuilder sb1= new StringBuilder(word1);
        StringBuilder sb2= new StringBuilder(word2);
        int count=0;
        System.out.println("length ! "+sb1.length());
        System.out.println("Length ! "+sb2.length());
        if(sb1.length()==sb2.length()){
            for(int i=0;i<sb1.length();i++){
                for(int k=0;k<sb2.length();k++){
                    if(sb1.charAt(i)==sb2.charAt(k)){
                        sb2.deleteCharAt(k);
                        count++;
                        System.out.println("Count is "+count);
                        break;
                    }
                }
            }

            if(count==sb1.length()){

                System.out.println("Anagrams!");
            }
            else{
                System.out.println("Not Anagrams");
            }
        }
        else{
            System.out.println("Not equal in length");
        }
    }
}

java - Javaのアナグラムアルゴリズム

35 に答える 35

Related

Reference