Programming

Leetcode-49. Group Anagrams

By PattySung 26 June 2023
Leetcode-49. Group Anagrams

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 1:

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

Example 2:

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

Example 3:

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

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

<解題>

  1. 用HashMap去建Map<String, ArrayList>，用排序後的字串為key
  2. 先把String 轉成 Char以排序 ->.toCharArray()
  3. 排序以作為key
  4. 再轉回String -> String.valueOf(str)

解法一


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()); //最後把map.values()的值，在新的ArrayList中回傳
    }
}

解法二


class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();

        for (String s : strs) {
            int[] charCounts = new int[26];
            // 统计字符串中每个字符的出现次数
            for (char c : s.toCharArray()) {
                charCounts[c - 'a']++;
            }

            // 将字符计数数组转换为唯一的字符串表示
            StringBuilder sb = new StringBuilder();
            for (int count : charCounts) {
                sb.append(count);
                sb.append('#'); // 使用 '#' 分隔字符计数
            }
            String key = sb.toString();

            // 将字符串添加到对应的分组中
            if (!map.containsKey(key)) {
                map.put(key, new ArrayList<>());
            }
            map.get(key).add(s);
        }

        return new ArrayList<>(map.values());
    }
}

{ “1#0#0#0#1#0#0#0#0#0#0#1#0#0#0#0#0#0#0#0#0#0#0#0#0#0#” => [“eat”, “tea”, “ate”], “1#0#0#0#1#0#0#0#0#0#0#1#0#0#0#0#0#0#0#0#0#0#0#0#0#0#” => [“tan”, “nat”], “0#0#0#0#0#1#0#0#0#0#0#0#0#0#0#0#0#0#0#1#0#0#0#0#0#0#” => [“bat”] }

map.values()-> [ [“eat”, “tea”, “ate”], [“tan”, “nat”], [“bat”] ]

Time: O(N * K * log(K)) Space: O(N * K) //k is the longest length of String