How to detect if two words are anagrams of eachother

08/11/2019

Two words are anagrams of each other if they can be formed by rearranging the letters of the others.

Anagrams can be detected by sorting the letters of the 2 words and checking that the sorted String are the same. The complexity is in O of n log n. It can be done by counting the letters in one word and in the other word and testing that they are the same. This method require a Map and is in O of n which is much faster.

Create the following java file:



import java.util.HashMap;
import java.util.Map;

public class InterviewAnagram {

    protected void updateIndex( Map<Character, Integer> index, char in, int nb ){
	
	if( !index.containsKey( in ) ){
	    index.put(in, nb);
	    return;
	}
	
	// Increment and add
	index.put(in, index.get(in)+nb);
    }
    
    public boolean isAnagram(String left, String right){
	// Input validation
	if ( left == null || right == null )
	    return false;
	
	char[] tab1 = left.toCharArray();
	char[] tab2 = right.toCharArray();
	
	if( tab1.length != tab2.length )
	    return false;
	
	Map<Character, Integer> index = new HashMap<Character, Integer>();

	// Loop on all the chars
	for(int i = 0 ; i < tab1.length ; i++){
	    updateIndex( index, tab1[i], 1);
	    updateIndex( index, tab2[i], -1);
	}
	
	
	for( Integer i : index.values() ){
	    if( i != 0 )
		return false;
	}
	
	// return the String found
	return true;
    }
    
    public static void main(String[] argv){
	InterviewAnagram o = new InterviewAnagram();
	String[] tab = {"abc","acb","aaa","bbb","bbbac"};
	
	for( String c : tab ){
	    System.out.println( "output[\"abc\", \""+c+"\"] = " + o.isAnagram("abc", c) );
	}
    }    
}

The output will be:

output["abc", "abc"] = true
output["abc", "acb"] = true
output["abc", "aaa"] = false
output["abc", "bbb"] = false
output["abc", "bbbac"] = false

For improving performance, the code adds the number of characters from the first word and remove the number of character the second word. At the end of the process the total number of all the characters should be 0. If a character has a value that is not 0, then the two words are not anagrams.

References:

Anagram Wikipedia