如何检查两个单词是否是字谜

hvelit 发布于 2019-02-28 algorithm 最后更新 2019-02-28 18:37 118 浏览

我有一个程序可以告诉你两个单词是否是另一个单词的字典。有几个例子不能正常工作,我希望有任何帮助,但如果它不是先进的,那将会很棒,因为我是第一年的程序员。 “校长”和“课堂”是彼此的变形,但是当我把“课堂”改为“课堂”时,它仍然说它们是字谜,我做错了什么?

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;
  }
}
已邀请:

nsequi

赞同来自:

排序方法不是最好的方法。它需要O(n)空间和O(nlogn)时间。相反,制作一个字符的哈希映射并对它们进行计数(增加第一个字符串中出现的字符并减少第二个字符串中出现的字符)。当某些计数达到零时,将其从哈希中删除。最后,如果两个字符串是字谜,那么哈希表最后将为空 - 否则它将不为空。 几个重要的笔记:(1)忽略字母案例和(2)忽略空格。 以下是C#中的详细分析和实现:Testing If Two Strings are Anagrams

tut

赞同来自:

使用较少变量的另一种解决方案如下。它使用O(n)时间复杂度。

public static boolean anagram(String s1, String s2) {
    if (s1.length() != s2.length()) return false;
s1 = s1.toLowerCase();
    s2 = s2.toLowerCase();
int sum = 0;
    for( int i=0; i<s1.length(); i++) {
        sum += (s1.charAt(i)-0) - (s2.charAt(i)-0);
    }
if ( sum == 0) return true;
return false;
}

kquis

赞同来自:

到目前为止,所有提出的解决方案都使用单独的char项,而不是代码点。我想提出两个解决方案来正确处理surrogate pairs(这些是由两个char项组成的字符from U+10000 to U+10FFFF)。 1)利用Java 8 CharSequence.codePoints()流的单行O(n logn)解决方案:

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;
}

eearum

赞同来自:

感谢您指出发表评论,在发表评论时我发现错误的逻辑。我更正了逻辑,并为每段代码添加了注释。

// 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;
}

zquam

赞同来自:

这是一个简单的快速O(n)解决方案,不使用排序或多个循环或哈希映射。我们递增第一个数组中每个字符的计数,并减少第二个数组中每个字符的计数。如果生成的计数数组充满零,则字符串为字谜。可以通过增加计数数组的大小来扩展以包含其他字符。

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]));
    }
}

ea_qui

赞同来自:

我们走两条相等长度的弦并跟踪它们之间的差异。我们不关心差异是什么,我们只想知道它们是否具有相同的字符。我们可以在O(n / 2)中执行此操作而无需任何后期处理(或许多素数)。

public class TestAnagram {
  public static boolean isAnagram(String first, String second) {
    String positive = first.toLowerCase();
    String negative = second.toLowerCase();
if (positive.length() != negative.length()) {
      return false;
    }
int[] counts = new int[26];
int diff = 0;
for (int i = 0; i < positive.length(); i++) {
      int pos = (int) positive.charAt(i) - 97; // convert the char into an array index
      if (counts[pos] >= 0) { // the other string doesn't have this
        diff++; // an increase in differences
      } else { // it does have it
        diff--; // a decrease in differences
      }
      counts[pos]++; // track it
int neg = (int) negative.charAt(i) - 97;
      if (counts[neg] <= 0) { // the other string doesn't have this
        diff++; // an increase in differences
      } else { // it does have it
        diff--; // a decrease in differences
      }
      counts[neg]--; // track it
    }
return diff == 0;
  }
public static void main(String[] args) {
    System.out.println(isAnagram("zMarry", "zArmry")); // true
    System.out.println(isAnagram("basiparachromatin", "marsipobranchiata")); // true
    System.out.println(isAnagram("hydroxydeoxycorticosterones", "hydroxydesoxycorticosterone")); // true
    System.out.println(isAnagram("hydroxydeoxycorticosterones", "hydroxydesoxycorticosterons")); // false
    System.out.println(isAnagram("zArmcy", "zArmry")); // false
  }
}
是的,此代码依赖于小写字符的ASCII英文字符集,但不应该很难修改为其他语言。你总是可以使用Map [Character,Int]来跟踪相同的信息,它会慢一些。

grem

赞同来自:

我用java编写了这个程序。我认为这也可能有所帮助:

public class Anagram {
    public static void main(String[] args) {
        checkAnagram("listen", "silent");
    }
public static void checkAnagram(String str1, String str2) {
        boolean isAnagram = false;
        str1 = sortStr(str1);
        str2 = sortStr(str2);
        if (str1.equals(str2)) {
            isAnagram = true;
        }
        if (isAnagram) {
            System.out.println("Two strings are anagram");
        } else {
            System.out.println("Two string are not anagram");
        }
}
public static String sortStr(String str) {
        char[] strArr = str.toCharArray();
        for (int i = 0; i < str.length(); i++) {
            for (int j = i + 1; j < str.length(); j++) {
                if (strArr[i] > strArr[j]) {
                    char temp = strArr[i];
                    strArr[i] = strArr[j];
                    strArr[j] = temp;
                }
            }
        }
        String output = String.valueOf(strArr);
        return output;
    }
}

daut

赞同来自:

public class Anagrams {
//Write aprogram to check if two words are anagrams
public static void main(String[] args) {
    Anagrams an=new Anagrams();
    System.out.println(an.isAnagrams("tree", "eetr"));
}
public boolean isAnagrams(String word1,String word2)
{
    boolean anagrams=false;
    char []arr1=word1.toCharArray();
    char []arr2=word2.toCharArray();
//They should be the same length
    int sum1=0;
    int sum2=0;
    for(int i=0;i<arr1.length;i++)
    {
        sum1+=(int)arr1[i];
        sum2+=(int)arr2[i];
    }
if(sum1==sum2)
    {
        anagrams=true;
    }
return anagrams;
}
}
Output:-
true

ncum

赞同来自:

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;
    }
}

podio

赞同来自:

这里有很复杂的答案。基于accepted answerthe comment提及'ac' - 'bb'问题,假设A = 1 B = 2 C = 3,我们可以简单地使用表示char的每个整数的平方来解决问题:

public boolean anagram(String s, String t) {
    if(s.length() != t.length())
        return false;
int value = 0;
    for(int i = 0; i < s.length(); i++){
        value += ((int)s.charAt(i))^2;
        value -= ((int)t.charAt(i))^2;
    }
    return value == 0;
}

ut_eos

赞同来自:

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;
}

ysit

赞同来自:

你应该使用这样的东西:

    for (int i...) {
        isFound = false;
        for (int j...) {
            if (...) {
                ...
                isFound = true;
            }
        }
isFound的默认值应为false。只是它

onam

赞同来自:

很多人提出了解决方案,但我只是想谈谈一些常见方法的算法复杂性:

  • 简单的“使用Arrays.sort()排序字符”的方法将是O(N log N)
  • 如果使用基数排序,则使用O(M)空格减少到O(N),其中M是字母表中不同字符的数量。 (英语是26分......但理论上我们应该考虑多语言字谜。)
  • 使用计数数组“计算字符数”也是O(N) ...并且比基数排序更快,因为您不需要重建已排序的字符串。空间使用情况为O(M)
  • 除非字母表很大,否则使用字典,散列图,树形图或等效字符“计算字符数”将比数组接近慢。
  • 在最糟糕的情况下,优雅的“素数产品”方法很遗憾O(N^2)这是因为对于足够长的单词或短语,素数的乘积将不适合long。这意味着您需要使用BigInteger,并且将BigInteger乘以一个小常量的N倍为O(N^2)。 对于假设的大字母表,缩放因子将很大。将素数乘积保持为BigInteger的最坏情况空间用法是(我认为)O(N*logM)
  • 如果单词不是字谜,则基于hashcode的方法通常为O(N)。如果哈希码相等,那么你仍然需要进行适当的anagram测试。所以这不是一个完整的解决方案。

godio

赞同来自:

一种解决这个问题的方法 - 基于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;
    }
}

cvitae

赞同来自:

 import java.util.Scanner;
public class AnagramTest {
   public static void main(String[] args) {
   System.out.println("Plz Enter Your First String: ");
   Scanner sc = new Scanner(System.in);
    String s1 = sc.nextLine();
   System.out.println("Plz Enter Your Second String: ");
String s2 = sc.nextLine();
    System.out.println(getAnagramString(s1,s2));
}
public static boolean getAnagramString(String s1,String s2){
   char[] c1 = s1.toCharArray();
   StringBuffer sb = new StringBuffer(s2);
for(char d: c1){
   int index = sb.indexOf(String.valueOf(d));       
     if(index !=-1){
         sb.deleteCharAt(index);
     }//if
     else{
         return false;
     }
}
return sb.length() ==0;
}
}

zquam

赞同来自:

类似的答案可能已经在C++中发布了,这里再次使用Java。请注意,最优雅的方式是使用Trie按排序顺序存储字符,但这是一个更复杂的解决方案。一种方法是使用哈希集来存储我们正在比较的所有单词,然后逐个进行比较。为了比较它们,制作一个字符数组,其索引表示字符的ANCII值(使用规范化器,因为即'a'的ANCII值为97),并且该值表示该字符的出现次数。这将在O(n)时间运行并使用O(m * z)空间,其中m是currentWord的大小,z是storedWord的大小,两者都为我们创建了Char []。

public static boolean makeAnagram(String currentWord, String storedWord){
    if(currentWord.length() != storedWord.length()) return false;//words must be same length
    Integer[] currentWordChars = new Integer[totalAlphabets];
    Integer[] storedWordChars = new Integer[totalAlphabets];
    //create a temp Arrays to compare the words
    storeWordCharacterInArray(currentWordChars, currentWord);
    storeWordCharacterInArray(storedWordChars, storedWord);
    for(int i = 0; i < totalAlphabets; i++){
        //compare the new word to the current charList to see if anagram is possible
        if(currentWordChars[i] != storedWordChars[i]) return false;
    }
    return true;//and store this word in the HashSet of word in the Heap
}
//for each word store its characters
public static void storeWordCharacterInArray(Integer[] characterList, String word){
    char[] charCheck = word.toCharArray();
    for(char c: charCheck){
        Character cc = c;
        int index = cc.charValue()-indexNormalizer;
        characterList[index] += 1;
    }
}

nnam

赞同来自:

如果两个单词包含相同数量的字符和相同的字符,则它们是彼此的字谜。您只需要按字典顺序对字符进行排序,并比较字符串a是否等于所有步骤中的字符串b。 这是一个代码示例。查看API中的Arrays以了解这里发生了什么。

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);
}

ket

赞同来自:

简单解决方案

    public class Java_Anagrams {
static boolean isAnagram(String a, String b) {
       char[] aArr = a.toUpperCase().trim().toCharArray();
       char[] bArr = b.toUpperCase().trim().toCharArray();
        if (aArr.length != bArr.length)
            return false;
        Arrays.sort(aArr);
        Arrays.sort(bArr);
        if(String.valueOf(aArr).equals(String.valueOf(bArr))){
            return true;
        }
        return false;
    }
    public static void main(String[] args) {
        String a = "Hello";
        String b =  "holle";
        boolean ret = isAnagram(a, b);
        System.out.println( (ret) ? "Anagrams" : "Not Anagrams" );
    }
}

frerum

赞同来自:

最快的算法是将26个英文字符中的每一个映射到唯一的素数。然后计算字符串的乘积。根据算术的基本定理,当且仅当它们的乘积相同时,2个字符串是字谜。

punde

赞同来自:

public static boolean isAnagram(String str1, String str2) {
    if( str1.length() != str2.length() ) return false;
    int str1Tot = 0;
    int str2Tot = 0;
    for( int i = 0 ; i < str1.length() ; i++) {
        str1Tot += str1.codePointAt(i);
        str2Tot += str2.codePointAt(i);
    }
    if( str1Tot == str2Tot ) return true;
    else return false;      
}

jautem

赞同来自:

恕我直言,最有效的解决方案是由@Siguza提供的,我把它扩展到了空间的字符串,例如:“威廉·莎士比亚”,“我是一个弱势的拼写者”,“学校大师”,“教室”

public int getAnagramScore(String word, String anagram) {
if (word == null || anagram == null) {
            throw new NullPointerException("Both, word and anagram, must be non-null");
        }
char[] wordArray = word.trim().toLowerCase().toCharArray();
        char[] anagramArray = anagram.trim().toLowerCase().toCharArray();
int[] alphabetCountArray = new int[26];
int reference = 'a';
for (int i = 0; i < wordArray.length; i++) {
            if (!Character.isWhitespace(wordArray[i])) {
                alphabetCountArray[wordArray[i] - reference]++;
            }
        }
        for (int i = 0; i < anagramArray.length; i++) {
            if (!Character.isWhitespace(anagramArray[i])) {
                alphabetCountArray[anagramArray[i] - reference]--;
            }
        }
for (int i = 0; i < 26; i++)
            if (alphabetCountArray[i] != 0)
                return 0;
return word.length();
}

in_ut

赞同来自:

这是我的解决方案。首先将字符串分解为char数组,然后对它们进行排序,然后比较它们是否相等。我猜这个代码的时间复杂度是O(a + b)。如果a = b我们可以说是O(2A)

public boolean isAnagram(String s1, String s2) {
StringBuilder sb1 = new StringBuilder();
        StringBuilder sb2 = new StringBuilder();
        if (s1.length() != s2.length())
            return false;
char arr1[] = s1.toCharArray();
        char arr2[] = s2.toCharArray();
        Arrays.sort(arr1);
        Arrays.sort(arr2);
for (char c : arr1) {
            sb1.append(c);
        }
for (char c : arr2) {
            sb2.append(c);
        }
System.out.println(sb1.toString());
        System.out.println(sb2.toString());
if (sb1.toString().equals(sb2.toString()))
            return true;
        else
            return false;
}

equia

赞同来自:

checkAnagram("THE END","DET NEH");
public void checkAnagram(String s3, String s4){
if(Arrays.equals(s3.replace(" ","").chars().sorted().toArray(), s4.replace(" ","").chars().sorted().toArray()))
            System.out.println( s3+ " and "+ s4 + " are Anagrams");
        else
            System.out.println("Not Anagrams");
    }

uanimi

赞同来自:

对不起,解决方案是在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;
    }

iut

赞同来自:

我看到没有人使用“哈希码”方法找出字谜。我发现我的方法与上面讨论的方法没什么不同,因此想到分享它。我写了下面的代码来找到在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;
            }
         }
    }

cvitae

赞同来自:

    /*
 * 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;
        //}
        }
}

godio

赞同来自:

如果对任一阵列进行排序,则解决方案将变为O(n log n)。但是如果你使用一个hashmap,那就是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;

aet

赞同来自:

其他一些解决方案没有排序

public static boolean isAnagram(String s1, String s2){
    //case insensitive anagram
StringBuffer sb = new StringBuffer(s2.toLowerCase());
    for (char c: s1.toLowerCase().toCharArray()){
        if (Character.isLetter(c)){
int index = sb.indexOf(String.valueOf(c));
            if (index == -1){
                //char does not exist in other s2
                return false;
            }
            sb.deleteCharAt(index);
        }
    }
    for (char c: sb.toString().toCharArray()){
        //only allow whitespace as left overs
        if (!Character.isWhitespace(c)){
            return false;
        }
    }
    return true;
}

nodio

赞同来自:

我有新的东西,我尝试使用XOR操作在O(n)中完成此操作。

public class TwoStringAnagram {
private static boolean isTwoStringsAnagram(String str1, String str2) {
        if (str1.length() < 2 && str2.length() < 2) return false;
        if (str1.length() != str2.length()) return false;
char[] charStr1 = str1.toCharArray();
        char[] charStr2 = str2.toCharArray();
int xorSum = 0;
        for (int i = 0; i < charStr1.length; i++) {
            xorSum = xorSum ^ charStr1[i] ^ charStr2[i];
        }
        return xorSum == 0;
    }
public static void main(String args[]) {
        String str1 = "ACT";
        String str2 = "TAC";
        System.out.println("Are input strings anagrams? " + isTwoStringsAnagram(str1, str2));
    }
}

uvero

赞同来自:

我知道这是一个老问题。但是,我希望这可以对某人有所帮助。该解决方案的时间复杂度为O(n ^ 2)。

public boolean areAnagrams(final String word1, final String word2) {
        if (word1.length() != word2.length())
            return false;
if (word1.equals(word2))
            return true;
if (word1.length() == 0 && word2.length() == 0)
            return true;
String secondWord = word2;
        for (int i = 0; i < word1.length(); i++) {
            if (secondWord.indexOf(word1.charAt(i)) == -1)
                return false;
secondWord = secondWord.replaceFirst(word1.charAt(i) + "", "");
        }
if (secondWord.length() > 0)
            return false;
return true;
}

id_cum

赞同来自:

我是C++开发人员,下面的代码是C++。我相信最快,最简单的方法是: 创建一个大小为26的整数向量,将所有槽初始化为0,并将该字符串的每个字符放入向量中的适当位置。请记住,向量按字母顺序排列,因此如果字符串中的第一个字母是z,它将进入myvector [26]。注意:这可以使用ASCII字符完成,所以基本上你的代码看起来像这样:

string s = zadg;
for(int i =0; i < s.size(); ++i){
    myvector[s[i] - 'a'] = myvector['s[i] - 'a'] + 1;
} 
因此,插入所有元素将花费O(n)时间,因为您只需遍历列表一次。你现在可以对第二个字符串执行完全相同的操作,并且也需要O(n)时间。然后,您可以通过检查每个插槽中的计数器是否相同来比较两个向量。如果它们是,那意味着你在两个字符串中都有相同数量的EACH字符,因此它们是字谜。两个向量的比较也应该花费O(n)时间,因为你只需要遍历它一次。 注意:该代码仅适用于单个字符。如果你有空格,数字和符号,你可以创建一个大小为96的矢量(ASCII字符32-127)而不是说 - 'a'你会说 - ''因为空格字符是第一个ASCII字符列表。 我希望有所帮助。如果我在某处犯了错误,请发表评论。

bquia

赞同来自:

这是在Java中使用HashMap的另一种方法

public static boolean isAnagram(String first, String second) {
    if (first == null || second == null) {
        return false;
    }
    if (first.length() != second.length()) {
        return false;
    }
    return doCheckAnagramUsingHashMap(first.toLowerCase(), second.toLowerCase());
}
private static boolean doCheckAnagramUsingHashMap(final String first, final String second) {
    Map<Character, Integer> counter = populateMap(first, second);
    return validateMap(counter);
}
private static boolean validateMap(Map<Character, Integer> counter) {
    for (int val : counter.values()) {
        if (val != 0) {
            return false;
        }
    }
    return true;
}
这是测试用例
@Test
public void anagramTest() {
    assertTrue(StringUtil.isAnagram("keep" , "PeeK"));
    assertFalse(StringUtil.isAnagram("Hello", "hell"));
    assertTrue(StringUtil.isAnagram("SiLeNt caT", "LisTen cat"));       
}

xquis

赞同来自:

在编写任何代码之前,数学家如何考虑问题:

  1. 字符串之间的关系“是anagrams”是等价关系,因此将所有字符串的集合划分为等价类。
  2. 假设我们有一个规则从每个班级中选择一个代表(婴儿床),那么通过比较他们的代表就可以很容易地测试两个班级是否相同。
  3. 一组字符串的明显代表是“按字典顺序排列的最小元素”,它可以通过排序从任何元素轻松计算。例如,包含'hat'的anagram类的代表是'aht'。
在你的例子中,“schoolmaster”和“theclassroom”是字谜,因为它们都在anagram类中,其中包括crib“acehlmoorsst”。 在伪代码中:
>>> def crib(word):
...     return sorted(word)
...
>>> crib("schoolmaster") == crib("theclassroom")
True

lmagni

赞同来自:

对于这么简单的任务来说似乎很尴尬。 首先, 你的循环太复杂了。尝试这样的事情。

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);
用于创建字符串。

sut

赞同来自:

public class Anagram {
public static void main(String[] args) {
String s1 = "abcdeaa11 fghijk lmnoAA";
    String s2 = "AAlmno1 edcba1fghijkaa";
    System.out.println(isAnagram(s1, s2));
}
private static String isAnagram(String s1, String s2) {
char[] array1 = s1.replaceAll("[\\s]", "").toLowerCase().toCharArray();
    char[] array2 = s2.replaceAll("[\\s]", "").toLowerCase().toCharArray();
    boolean anagram = false;
    List<Character> list = new LinkedList<Character>();
for (int i = 0; i < array1.length; i++) {
        list.add(array1[i]);
    }
    for (int i = 0; i < array2.length; i++) {
        if (list.isEmpty()) {
            break;
        }
        if (list.contains(array2[i]))
            list.remove((Object) array2[i]);
if (i == array1.length - 1 && list.isEmpty())
            anagram = true;
     }
    if (anagram)
        return "The given strings are anagrams";
return "The strings are not anagrams";
}
}

punde

赞同来自:

一种简单的方法来确定testString是否是baseString的anagram。

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;
}

nsunt

赞同来自:

通过使用更多内存(最多N / 2个元素的HashMap),我们不需要对字符串进行排序。

public static boolean areAnagrams(String one, String two) {
    if (one.length() == two.length()) {
        String s0 = one.toLowerCase();
        String s1 = two.toLowerCase();
        HashMap<Character, Integer> chars = new HashMap<Character, Integer>(one.length());
        Integer count;
        for (char c : s0.toCharArray()) {
            count = chars.get(c);
            count = Integer.valueOf(count != null ? count + 1 : 1);
            chars.put(c, count);
        }
        for (char c : s1.toCharArray()) {
            count = chars.get(c);
            if (count == null) {
                return false;
            } else {
                count--;
                chars.put(c, count);
            }
        }
        for (Integer i : chars.values()) {
            if (i != 0) {
                return false;
            }
        }
        return true;
    } else {
        return false;
    }
}
对于对字符串进行排序的解决方案,此函数实际上在O(N)...而不是O(NlogN)中运行。如果我假设你只使用字母字符,我只能使用26个整数的数组(从a到z没有重音或装饰)而不是hashmap。 如果我们定义: N = | one | + |两个| 我们在N上进行一次迭代(一次超过一次以增加计数器,一次减少超过两次)。 然后检查我们在mose N / 2迭代的总数。 所描述的其他算法有一个优点:它们不使用额外的内存,假设Arrays.sort使用QuickSort的原位版本或合并排序。但是既然我们在谈论字谜,我会假设我们正在谈论人类语言,因此单词不应该长到足以给出记忆问题。

hipsum

赞同来自:

完美的工作!但不是一个好方法,因为它运行在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;
}

nea

赞同来自:

O(n)解决方案没有任何排序并且只使用一个映射。

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;
}