Friday, May 17, 2013

There is a stream of words which contains Anagrams. How would you print anagrams in a single bucket from that stream ?

Sort each word and then see if the two words are equal ? abba, baab, abab should go to the same bucket.
Simple method to check if two Strings are anagrams

public boolean isAnagram(String s1, String s2){ 
char[] a1 = s1.toCharArray(); 
char[] a2 = s2.toCharArray(); 
Arrays.sort(a1); 
Arrays.sort(a2); 
if (Arrays.toString(a1).equals(Arrays.toString(a2))){ 
return true; 
} 
return false; 
}
Algorithm
1) Use a hashmap with string as key and list<string> as value where list of strings contain all anagrams of a given key string.
2) For each word in the input array, create a key by sorting the word and put this word to that list whose key is the sorted word. for example [aakk -> akka, akak] If it does not exist then create a new list with the sorted word as key in map.

3) Print all strings from the list whose key is the input word(sorted string).
Source Code

import java.util.*;

public class Anagrams {
    private static Map<String,List<String>> anagramsMap = new HashMap<>(100);
    public static void main(String[] args) {

        String[] input = {
            "akka", "akak", "baab", "baba", "bbaa"
        };

        for (String s: input) {
            char[] word = s.toCharArray();
            Arrays.sort(word);
            String key = String.valueOf(word);
            if (!anagramsMap.containsKey(key)) {
                anagramsMap.put(key, new ArrayList < String > ());
            }

            anagramsMap.get(key).add(s);
        }

        System.out.println("anagramsMap = " + anagramsMap);
    }
}
Time Complexity
If we ignore the time consumed by sorting an individual string then we can say that the above approach takes Big O(n) time complexity. Otherwise the actual time complexity would be N log N (sorting) + N (compare)

No comments:

Post a Comment

Your comment will be published after review from moderator