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

Question

我有一个程序,可以显示两个单词是否是彼此的字谜.有一些例子不能正常工作,我会感激任何帮助,虽然如果它不是先进的那将是伟大的,因为我是一年级的程序员."校长"和"教室"是彼此的字谜,然而当我把"教室"改为"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

如果两个单词包含相同数量的字符和相同的字符,则它们是彼此的字谜.您只需要按字典顺序对字符进行排序,并确定一个字符串中的所有字符是否与另一个字符串中的所有字符相同且顺序相同.

这是一个代码示例.Arrays在API中查看以了解这里发生了什么.

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).但是如果你使用一个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;

Answer 4

这是一个简单的快速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]));
    }
}

Answer 5

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

• 简单的"使用字符排序Arrays.sort()"方法将是O(N log N).

• 如果您使用的基数排序,可以降低因O(N)与O(M)空间,其中M是字母表中不同的字符数.(这是26英文...但理论上我们应该考虑多语言字谜.)

• 使用计数数组"计算字符数"也是O(N)......并且比基数排序更快,因为您不需要重新构建排序的字符串.空间使用将是O(M).

• 除非字母表很大,否则使用字典,散列映射,树形图或等效字符"计算字符数"将比数组接近慢.

• 不幸O(N^2)的是,在最坏的情况下,优雅的"素数产品"方法是因为对于足够长的单词或短语,素数的乘积不适合于long.这意味着你需要使用BigInteger,并且N乘以BigInteger一个小常数O(N^2).

  对于假设的大字母表,缩放因子将会很大.BigInteger(我认为)最糟糕的空间使用来保持素数产品O(N*logM).

• 如果单词不是字谜,hashcode通常采用基础方法O(N).如果哈希码相等,那么你仍然需要进行适当的anagram测试.所以这不是一个完整的解决方案.

Answer 6

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