How to check if two words are anagrams

Question

I have a program that shows you whether two words are anagrams of one another. There are a few examples that will not work properly and I would appreciate any help, although if it were not advanced that would be great, as I am a 1st year programmer. "schoolmaster" and "theclassroom" are anagrams of one another, however when I change "theclassroom" to "theclafsroom" it still says they are anagrams, what am I doing wrong?

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

I had written this program in java. I think this might also help:

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

Answer 2

I know this is an old question. However, I'm hoping this can be of help to someone. The time complexity of this solution is 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;
}

Answer 3

Fastest algorithm would be to map each of the 26 English characters to a unique prime number. Then calculate the product of the string. By the fundamental theorem of arithmetic, 2 strings are anagrams if and only if their products are the same.

Answer 4

Here is another approach using HashMap in Java

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

Here is the test case

@Test
public void anagramTest() {
    assertTrue(StringUtil.isAnagram("keep" , "PeeK"));
    assertFalse(StringUtil.isAnagram("Hello", "hell"));
    assertTrue(StringUtil.isAnagram("SiLeNt caT", "LisTen cat"));       
}

Answer 5

So far all proposed solutions work with separate char items, not code points. I'd like to propose two solutions to properly handle surrogate pairs as well (those are characters from U+10000 to U+10FFFF, composed of two char items).

1) One-line O(n logn) solution which utilizes Java 8 CharSequence.codePoints() stream:

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

2) Less elegant O(n) solution (in fact, it will be faster only for long strings with low chances to be anagrams):

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 6

Two words are anagrams of each other if they contain the same number of characters and the same characters. You should only need to sort the characters in lexicographic order, and determine if all the characters in one string are equal to and in the same order as all of the characters in the other string.

Here's a code example. Look into Arrays in the API to understand what's going on here.

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