LeetCode 49: 字母異位詞分組 Group Anagrams

題目:

給定一個字元串數組，将字母異位詞組合在一起。字母異位詞指字母相同，但排列不同的字元串。

Given an array of strings, group anagrams together.

示例:

輸入: ["eat", "tea", "tan", "ate", "nat", "bat"],
輸出:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]           

說明：

• 所有輸入均為小寫字母。
• 不考慮答案輸出的順序。

Note:

• All inputs will be in lowercase.
• The order of your output does not matter.

解題思路:

​ 題目要求是 不管字母怎樣排序隻要字母相同都歸為一類, 隻要把所有單詞的字母按一定規律排列好, 隻要每個單詞的字母按規律排好後組成的字元串相同, 則歸為一類

排序字母解題:

​ 用哈希映射

{Key : Value}

Key 為排好序的字元串, Value 為數組, 存儲與 Key 字母相同的單詞, 周遊每個單詞并排序字母, 查找排序好的字元串是否存在于 Keys, 利用哈希映射可将查找操作時間複雜度降為 O(1)

其解題邏輯為(這裡按字母升序排列):

輸入: ["eat", "tea", "tan", "ate", "nat", "bat"]
建立哈希映射 map = {}
周遊該字元串數組:

第一個單詞: "eat" --> "aet"
"aet" 不存在于 map, 建立映射 {"aet" : [ "eat" ] }

第二個單詞: "tea" --> "aet"
"aet" 存在于 map, 加入其 Values {"aet" : [ "eat" , "tea" ] }

第三個單詞: "tan" --> "ant"
"ant" 不存在于 map, 建立映射  {"aet" : [ "eat" , "tea" ] ; "ant" : [ "tan" ] }

第四個單詞: "ate" --> "aet"
"aet" 存在于 map, 加入其 Values {"aet" : [ "eat" , "tea" , "ate" ] ; "ant" : [ "tan" ] }

......

map = {"aet" : [ "eat" , "tea" , "ate" ] ; "ant" : [ "tan" , "nat"] ; "abt" : [ "bat" ] }

傳回該哈希映射的 Values 組成的數組:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]           

複雜度:

• 時間複雜度：O(N*(K*logK))，其中 N 是 strs 的長度，而 K 是 strs 中字元串的最大長度。周遊每個字元串時複雜度為 O(N)。使用内置排序函數排序字元串中的字母的時間複雜度為 O(K*logK)。
• 空間複雜度：O(N*K)，存儲在 map 中資料所占用的空間。

統計字頻解題:

這種解題方法還可以再優化, 可以省略對字元串排序的操作。

仔細想想,一個單詞最多由 26 個英文字母組成, 不就也可以建立一個哈希映射嗎? 如:

對于單詞 "aeat" :
建立哈希映射{ 'a' : 2 ; 'e' : 1; t : 1 }           

key 為出現的單詞, value 出現的頻次。如果周遊每個 key 判斷字母是否相等, 再判斷出現次數是否相等, 這顯然是更複雜了。

可以将每個字母出現的頻次組成連續字元:

每個字母 a-z 出現頻次: [2,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0]
組成字元串: "20001000000000000001000000"           

隻需判斷每個單詞的字母頻次字元串是否相同就可以了。

對于求詞頻還可以優化, 字母數量固定 26 個, 直接建立一個長度為 26 的數組, 其索引代表二十六個字母位, 周遊單詞中的字母, 字母每出現一次, 數組中代表該字母的元素值加 1。

這樣就避免了排序操作

Java:

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        if(strs.length==0) return new ArrayList<>();
        Map<String, List<String>> map = new HashMap<>();//建立映射關系
        for (String s : strs) {//周遊該字元串數組
            char[] chs = s.toCharArray();//轉成字元
            Arrays.sort(chs);//排序字元串字母
            String key = String.valueOf(chs);//轉成字元串
            if(!map.containsKey(key)) map.put(key, new ArrayList<>());//如果 key 不存在, 建立映射關系
            map.get(key).add(s);//加入其對應的 Value 所在的數組
        }
        return new ArrayList(map.values());//傳回 Values 組成的數組
    }
}           

Python:

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        ans = collections.defaultdict(list) # 建立映射關系
        for s in strs: # 周遊該字元串數組
            ans[tuple(sorted(s))].append(s) # sorted(s):排序字元串字母, 并加入其對應的 Value 所在的數組
        return ans.values() # 傳回 Values 組成的數組           

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        if (strs.length == 0) return new ArrayList<>();
        Map<String, List<String>> map = new HashMap<>();// 建立映射關系
        for (String s : strs) {//周遊該字元串數組
            int[] count = new int[26];//建立一個 26 字母的映射關系
            for (char c : s.toCharArray()) count[c - 'a']++;//周遊字字元串每個字母統計每個字母出現的頻次
            String key = Arrays.toString(count);//轉成字元串
            if (!map.containsKey(key)) map.put(key, new ArrayList<>());//如果 key 不存在, 建立映射關系
            map.get(key).add(s);//加入其對應的 Value 所在的數組
        }
        return new ArrayList(map.values());//傳回 Values 組成的數組
    }
}           

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        ans = collections.defaultdict(list)# 建立映射關系
        for s in strs: # 周遊該字元串數組
            count = [0] * 26 # 建立一個 26 字母的映射關系
            for c in s: # 周遊字字元串每個字母
                count[ord(c) - 97] += 1 # 每個字母出現的頻次(元素值)加1
            ans[tuple(count)].append(s) # 加入其對應的 Value 所在的數組
        return ans.values() # 傳回 Values 組成的數組           

歡迎關注微信.公..衆号: 愛寫Bug