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"].

What is Anagram?

• Two strings are anagram if they can be the same after change the order of characters.

思路

• HASHMAP<sorted str, ArrayList<orig str>>，帮助判断是否为变
• ArrayList<orig str>： 可以记录每一类都多少个相同的变形词
• 检查是否是anagrams：将每个str排序，如果相同则代表为anagrams；否则，不是。

1. 将sort以后str放入map 的 KEY，orign作为value。
   • 对String sort时，需转换成char[] charTemp
   • 对char[]排序完成后，再将其转换回String： String.valueOf(charTemp)
2. 全部放到hashmap以后，遍历hashmap，将value不止一个元素的取出来放到result中

public class Solution {
    /**
     * @param strs: A list of strings
     * @return: A list of strings
     */
    public List<String> anagrams(String[] strs) {
        // write your code here
        // 思路：HASHMAP<sorted str, ArrayList<orig str>>，帮助判断是否为变形词
        // ArrayList<orig str>： 可以记录每一类都多少个相同的变形词
        // 检查是否是anagrams：将每个str排序，如果相同则代表为anagrams。否则不是
        // 1. 将sort以后str放入map 的 KEY，orign作为value。
        // 2. 全部放到HASHMAP以后，遍历HASHMAP，将VALUE不止一个元素的取出来放到RESULT中
        
        List<String> result = new ArrayList<String>();
        
        if (strs == null || strs.length == 0) {
            return result;
        }
        
        HashMap<String, ArrayList<String>> mapping = new HashMap<>();
        
        for (String curStr : strs) {
            char[] tempChar = curStr.toCharArray();
            Arrays.sort(tempChar);
            String sortedStr = String.valueOf(tempChar);
            
            if (mapping.containsKey(sortedStr)) { //duplicated
                ArrayList<String> sub = mapping.get(sortedStr);
                sub.add(curStr);
                mapping.put(sortedStr, sub);
            } else {  //new 
                ArrayList<String> sub = new ArrayList<String>();
                sub.add(curStr);
                mapping.put(sortedStr, sub);
            }
        }
        
        // get all duplicated strs from mapping where value size > 1
        for (Map.Entry<String, ArrayList<String>> entry : mapping.entrySet()) {
            if (entry.getValue().size() > 1) {
                result.addAll(entry.getValue());
            }
        }
        return result;
    }
}