CareerCup

Set a prime number for each of the letters a to z say 2 to 101. Now, all anagram can be represented by a unique number which can be calculated as a product of all the numbers associated the characters in the word. For example: Boy and Yob are anagrams and the associated numbers are : 3x47x97 and 97x47x3 respectively, which are equal.

So, keep a hashmap with the primeproduct as the key and the list of same anagrams as the value.

public class Anagrams
{
	int primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101}
	private static int hash(String word)
	{
		int hash = 0;

		word = word.toLower();
		for(int i=0; i< word.length(); i++)
			hash*=primes[word[i] - ‘a’];

		return hash;
	} 

	public static void anagrams(String fileContent)
	{
		String[] words = fileContent.trim().split(“ ”, false);
		HashMap<Integer, HashSet<String>> anagrams;
		for(int i=0; i<words.length; i++)
		{
			int wordKey = hash(word);
			if(!anagrams.contains(wordKey))
				anagrams.put(wordKey, new HashSet<String());
			
			anagrams.get(wordKey).add(word);
		}
		
		print(anagrams);
	}
}

Use Hashes:

Have a Hashmap<Integer,HashSet<String>> words. For each String
1. compute its hash
2. If the hash is not in the words map put it together with the a new Hashset called anagrams which contains the current String.
3. If it is in the map make sure the string is not in the anagrams map
4.if it isn't in the anagrams map update the anagrams map with that word
5. After you've reached the end of the email iterate over all the keys in the words map and get the unique anagram lists.

Time complexityO(N) space complexity O(N)

This has been asked so often since I started coming here (6 weeks).

use trie
While storing a word in trie, sort it using a count [] array , and then sort.

public static void allAnagrams(String s) {
		String[] input = s.toLowerCase().replaceAll("[^\\s^a-z]", "").split("\\s");
		
		HashMap<Integer, HashMap<String, LinkedList<String>>> hm = new HashMap<Integer, HashMap<String,LinkedList<String>>>();
		
		for (int i = 0; i < input.length; i++) {
			String current = input[i];
			int currentLenght = current.length();
			
			if (hm.containsKey(currentLenght)) {
				HashMap<String, LinkedList<String>> hhm = hm.get(currentLenght);
				
				// create the key
				char[] chars = current.toCharArray();
				Arrays.sort(chars);				
				String key = new String(chars);
				
				if (hhm.containsKey(key)) {
					LinkedList<String> ll = hhm.get(key);
					ll.add(current);
				}
				else {
					// create the list and add current
					LinkedList<String> ll = new LinkedList<String>();
					ll.add(current);
					
					// map key to list
					hhm.put(key, ll);
				}
			}
			else {
				HashMap<String, LinkedList<String>> hhm = new HashMap<String, LinkedList<String>>();
				
				// create the key
				char[] chars = current.toCharArray();
				Arrays.sort(chars);				
				String key = new String(chars);
				
				// create the linked list and add current
				LinkedList<String> ll = new LinkedList<String>();
				ll.add(current);
				
				hhm.put(key, ll);
				hm.put(currentLenght, hhm);
			}
		}
		
		Iterator<Integer> i = hm.keySet().iterator();
		
		while(i.hasNext()) {
			int currentKey = i.next();
			System.out.println("Anagrams of length: " + currentKey);
			
			HashMap<String, LinkedList<String>> hhm = hm.get(currentKey);
			
			Iterator<String> ii = hhm.keySet().iterator();
			
			while(ii.hasNext()) {
				String key = ii.next();
				System.out.print("  ");
				System.out.println("Anagrams composed of letters: " + key);
				
				LinkedList<String> ll = hhm.get(key);
				for (int j = 0; j < ll.size(); j++) {
					System.out.println("    " + ll.get(j));
				}
			}
		}
		
		System.out.println();
	}

Create a Hash Map <String , String >;
Pick word by word , sort and the save the orignal string in hash map
Every Time you save word , concatinate it with the index value
example        { "abc","cda","dca" }
           sort
                     all became "abc"
           Concatinate Hash_map["abc"]="abc";
           Concatinate Hash_map["abc"]="abc , cda";
           Concatinate Hash_map["abc"]="abc , cda, dca";

C++ version.

#include <iostream>
#include <regex>
#include <iterator>
#include <map>
#include <unordered_set>
#include <algorithm>

int main() {
	std::string content = "Mr. Adam Mada, what's a carthorse? Must be some kind of orchestra! "
        "Did you know that 'dama' is lady in portuguese?";
    
    // Remove punctuaction from mail content
    content.erase(std::remove_if(content.begin(), content.end(), [](char c) {
        return !std::isalpha(c) && !std::isspace(c);
    }), content.end());
    
    // Split all words
    std::regex re("\\s+");
	std::sregex_token_iterator rti(content.begin(), content.end(), re, -1);
	std::vector<std::string> words {rti, std::sregex_token_iterator()};
    
    // Create a map where the key is each word in it's sorted form.
    // The value of the map is a set of all corresponding anagrams.
    std::map<std::string, std::unordered_set<std::string>> words_map;
    for (std::string& word : words) {
        if (word.size() < 2)
            continue;
        
        std::transform(word.begin(), word.end(), word.begin(), ::tolower);
        std::string sorted_word(word);
        std::sort(sorted_word.begin(), sorted_word.end());
        auto it = words_map.find(sorted_word);
        if (it == words_map.end()) {
            words_map.emplace(sorted_word, std::unordered_set<std::string>{word});
        } else {
            auto& words = it->second;
            words.insert(word);
        }
    }
    
    // Print all anagrams
    for (const auto& p : words_map) {
        const auto& words = p.second;
        if (words.size() > 1) {
            std::copy(words.begin(), words.end(), std::ostream_iterator<std::string>(std::cout, " "));
            std::cout << std::endl;
        }
    }
    
	return 0;
}

static void findAnagram(String[] str) {
		HashMap<String, HashSet<String>> map = new HashMap<String, HashSet<String>>();
		for (int i = 0; i < str.length; i++) {
			char[] arr = str[i].toCharArray();
			Arrays.sort(arr);
			String key = new String(arr);
			if (!map.containsKey(key)) {
				HashSet<String> set = new HashSet<String>();
				map.put(key, set);
			}
			HashSet<String> tmp = map.get(key);
			if (!tmp.contains(str[i])) {
				tmp.add(str[i]);
			}

		}
		for (String key : map.keySet()) {
			System.out.println(map.get(key).toString());
		}

}

javascript version:

var map = {
    hashMap: [],
    get: function(key) {
        return this.hashMap[key];
    },
    has: function(key) {
        return this.get(key)!=null && this.get(key)!=undefined;
    },
    put: function(key, word) {
        var words = this.get(key)||[];
        console.debug("putting", word, "with", key, "in", words);
        words.push(word);
        this.hashMap[key]=words;
        console.debug(this.hashMap)
    },
    toString: function() {
        console.debug(this.hashMap);       
    }
}

var hash=function(word) {
    var primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101];
    var key = 1;
            
    for(var i=0; i<word.length; i++) {
        key*=primes[word[i].charCodeAt(0) - 'a'.charCodeAt(0)]
    }
    return key;
}

var words=["hi", "bye", "ih"];

for(word in words) {
    word = words[word];
    var key = hash(word);
   
    map.put(key, word);
    
}

console.debug(map.toString());