專欄：50多種數據結構徹底征服

專欄：50多種經典圖論算法全部掌握

最近一網友收到一個更好的offer，感覺華為開的有點低了，想解約華為，又擔心會浪費華為的一個hc，影響部門hr的績效。其實我覺得這種擔心是多余了，去華為面試沒有被錄取的太多了，你不去了他們完全可以在找一個替補的。在說你是一個13a，這基本上是最低級別的，去不去都沒有任何影響，如果你是18級以上估計hr還會爭取一下。所以想走就走吧，不要猶豫不決。

--------------下面是今天的算法題--------------

來看下今天的算法題，這題是LeetCode的第49題：字母異位詞分組。

問題描述

來源：LeetCode第49題

難度：中等

給你一個字符串數組，請你將字母異位詞組合在一起。可以按任意順序返回結果列表。 字母異位詞 是由重新排列源單詞的所有字母得到的一個新單詞。

示例1：

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

• 1 <= strs.length <= 10^4

• 0 <= strs[i].length <= 100

• strs[i] 僅包含小寫字母

問題分析

這題是讓把相同的字母異位詞分到一組，判斷兩個字符串是否是字母異位詞有兩種方式， 一種是對每個字符串中的所有字母排序 ，如果兩個字符串中字母排序的結果是一樣的，那么這兩個字符串就是字母異位詞。

比如字符串“bcac”排序之后是“abcc”，字符串“cbac”排序之后也是“abcc”，所以字符串“bcac”和字符串“cbac”是字母異位詞。

還一種方式是統計每個字符串中每個字符出現的次數 然后轉化為字符串，比如字符串“bcac”可以轉化為“112”，表示有1個a，1個b，2個c。字符串“cbac”也可以轉化為112”，所以字符串“bcac”和字符串“cbac”是字母異位詞。

第一種方式比較簡單，但需要排序，效率不如第二種，我們這里用第二種方式來看下代碼。

JAVA：

public List
           
 > groupAnagrams(String[] strs) {     Map > map =  new HashMap<>();      for (String str : strs) {          char[] ch =  new  char[ 26];          // 統計字符串中每個字符串出現的次數          for ( char c : str.toCharArray())             ch[c -  'a']++;          // 轉化為字符串。         String keyStr = String.valueOf(ch);          if (!map.containsKey(keyStr))             map.put(keyStr,  new ArrayList<>());         map.get(keyStr).add(str);     }      return  new ArrayList<>(map.values()); }

C++：

public:
    vector

 > groupAnagrams(vector

  &strs) {         unordered_map

 > mp;         for (string &str: strs) {             vector

  ch(26, 0);             // 統計字符串中每個字符串出現的次數             for (char c: str)                 ch[c - 'a']++;             // 轉化為字符串。             string keyStr = string(ch.begin(), ch.end());             mp[keyStr].emplace_back(str);         }         vector

 > res;         for (auto &it: mp) {             res.emplace_back(it.second);         }         return res;     }

Python：

def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
    mp = collections.defaultdict(list)
    for str in strs:
        #  統計字符串中每個字符串出現的次數
        ch = [0] * 26
        for c in str:
            ch[ord(c) - ord('a')] += 1
        # 將列表轉換為元組，作為鍵，將當前字符串添加到值中
        mp[tuple(ch)].append(str)
    return [value for value in mp.values()]

筆者簡介

博哥，真名：王一博，畢業十多年， 作者，專注于 數據結構和算法 的講解，在全球30多個算法網站中累計做題2000多道，在公眾號中寫算法題解800多題，對算法題有自己獨特的解題思路和解題技巧，喜歡的可以給個關注，也可以 下載我整理的1000多頁的PDF算法文檔 。