LeetCode 49. Group Anagrams (Java)

tags: leetcode Java hashmap

Description

Given an array of strings strs, group the anagrams together. You can return the answer in any order.
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

給一字符串數組, 將錯位詞(指相同字符不同排列的字符串) 分組

Example

Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

Input: strs = [""]
Output: [[""]]

Idea

• 利用迴圈將string陣列分類進map
• 整個程式碼運用到List及Map的語法(List有兩種實現類：ArrayList,LinkedList)
• Array和ArrayList的差別 Map用法
• 最後回傳時，要map裡的value轉換成ArrayList才可回傳

Code

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, ArrayList<String>> map = new HashMap<>();
        
        for (String s: strs){
            char[] key_str = s.toCharArray();//string 轉成char 為了排序
            Arrays.sort(key_str);
            String key = String.valueOf(key_str);//轉回string
            if(map.containsKey(key)){//判斷此key是否在map
               map.get(key).add(s); //有的話將s加入該key的value中
            }
            else{
                map.put(key, new ArrayList<>());//沒有的話將key加入map，並在value建立一個類別
                map.get(key).add(s);
            }
                
        }
        return new ArrayList<>(map.values());
    }
}

Result

Runtime: 6 ms, faster than 80.28% of Java online submissions for Group Anagrams.
Memory Usage: 42 MB, less than 81.58% of Java online submissions for Group Anagrams.