Anagrams

LintCode-171.Anagrams

Given an array of strings, return all groups of strings that are anagrams.

Notice: All inputs will be in lower-case.

Example

Given ["lint", "intl", "inlt", "code"], return ["lint", "inlt", "intl"].

Given ["ab", "ba", "cd", "dc", "e"], return ["ab", "ba", "cd", "dc"].

Challenge

What is Anagram?

  • Two strings are anagram if they can be the same after change the order of characters.
public class Solution {
    /**
     * @param strs: A list of strings
     * @return: A list of strings
     */
    public List<String> anagrams(String[] strs) {
        List<String> result = new ArrayList<>();
        if (strs == null || strs.length == 0) {
        	return result;
        }

        HashMap<String, List<String>> map = new HashMap<>();

        for (String str : strs) {
        	String sortedStr = sortString(str);

        	if (map.containsKey(sortedStr)) {
        		map.get(sortedStr).add(str);
        	} else {
        	    List<String> list = new ArrayList<>();
        	    list.add(str);
        	    
        		map.put(sortedStr, list);
        	}
        }

        for (List<String> list : map.values()) {
        	if (list.size() > 1) {
        		result.addAll(list);
        	}
        }
        
        return result;
    }
    
    String sortString(String s) {
    	char[] charArray = s.toCharArray();
    	Arrays.sort(charArray);

    	return new String(charArray);
    }
}

Hope this helps,
Michael

DigitalOcean Referral Badge