3
\$\begingroup\$

Two strings are anagrams if they are permutations of each other. Assuming we have an ASCII alphabet we can take 128 integer array to count the characters in the first string. Then decrement the count for the corresponding character in the second string. If all the character counts are zero then the strings are anagrams else they are not.

public class anagrams {
        public static boolean anagramsHelper(String[] words)
        {
            for(int i = 1 ; i < words.length ; i++)
            {
                if(!areAnagrams(words[0], words[i]))
                {
                    return false;
                }
            }
            return true;
        }
        public static boolean areAnagrams(String word1, String word2)
        {
            if(word1.length() != word2.length())
            {
                return false; // anagrams are strings with same length
            }
            int[] charCount = new int[128]; // 128 unique chars in ASCII
            //count the chars in word1
            for(int i = 0 ; i < word1.length() ; i++)
            {
                charCount[(int)word1.charAt(i)]++;
            }
            //decrement the char count for chars in word2
            for(int i = 0 ; i < word2.length() ; i++)
            {
                if(charCount[(int)word2.charAt(i)] == 0)
                {
                    return false;
                }
                charCount[(int)word2.charAt(i)]--;
            }
            //verify if any char count is non zero
            //for anagrams it should be zero else they are not anagrams
            for(int i  = 0 ; i < 128 ; i++)
            {
                if(charCount[i] != 0)
                {
                    return false;
                }
            }
            return true;
        }
        public static void main(String[] args) {
            String[] words = {"abc", "bca", "cab" , "myd"};
            System.out.println(anagramsHelper(words));
        }
    }
\$\endgroup\$
2
\$\begingroup\$

1

class anagrams: in Java, class names must begin with a capital letter.

2

You restrict yourself to ASCII. However, you could use a HashMap<Character, Integer>. Of course, it implies larger constant factor, yet it matches the linear time complexity of your implementation.

Summa summarum

I thought about this:

public static boolean areAnagrams(String word1, String word2) {
    if (word1.length() != word2.length()) {
        return false;
    }

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

    for (char c : word1.toCharArray()) {
        map.put(c, map.getOrDefault(c, 0) + 1);
    }

    for (char c : word2.toCharArray()) {
        int count = map.getOrDefault(c, 0) - 1;

        if (count < 0) {
            return false;
        }

        map.put(c, count);
    }

    return true;
}

Hope that helps.

\$\endgroup\$
  • \$\begingroup\$ that's true for time complexity, but maps use extra space right? The underlying implementation of map stores the data as pairs. \$\endgroup\$ – saneGuy Apr 18 '16 at 16:35
  • \$\begingroup\$ Extra space, yes. Also, even if the load factor of your HashMap is reasonable, the map works in average constant time, but not as fast as an array lookup. \$\endgroup\$ – coderodde Apr 18 '16 at 16:38
  • \$\begingroup\$ cool. Also for other character sets if we know the size of the alphabet we can use the same logic with different array size. \$\endgroup\$ – saneGuy Apr 18 '16 at 17:50
  • \$\begingroup\$ I know that char takes two bytes, and thus, has 65536 possible values, yet I am not an expert on Unicode -- or anything related to encodings -- so hard to tell. \$\endgroup\$ – coderodde Apr 18 '16 at 17:54
  • \$\begingroup\$ Using HashMap adapts to space, whereas using an array adapts to speed. It depends on context, which one is more important. \$\endgroup\$ – coderodde Apr 18 '16 at 17:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.