Question

49. 字母异位词分组

English Version

题目描述

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

 

示例 1:

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

示例 2:

输入: strs = [""]
输出: [[""]]

示例 3:

输入: strs = ["a"]
输出: [["a"]]

 

提示：

• 1 <= strs.length <= 104
• 0 <= strs[i].length <= 100
• strs[i] 仅包含小写字母

解法

方法一：哈希表

1. 遍历字符串，对每个字符串按照字符字典序排序，得到一个新的字符串。
2. 以新字符串为 key，[str] 为 value，存入哈希表当中（HashMap<String, List<String>>）。
3. 后续遍历得到相同 key 时，将其加入到对应的 value 当中即可。

以 strs = ["eat", "tea", "tan", "ate", "nat", "bat"] 为例，遍历结束时，哈希表的状况：

key	value
"aet"	["eat", "tea", "ate"]
"ant"	["tan", "nat"]
"abt"	["bat"]

最后返回哈希表的 value 列表即可。

时间复杂度 $O(n\times k\times \log k)$。其中 $n$ 和 $k$ 分别是字符串数组的长度和字符串的最大长度。

class Solution:
  def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
    d = defaultdict(list)
    for s in strs:
      k = ''.join(sorted(s))
      d[k].append(s)
    return list(d.values())

class Solution {
  public List<List<String>> groupAnagrams(String[] strs) {
    Map<String, List<String>> d = new HashMap<>();
    for (String s : strs) {
      char[] t = s.toCharArray();
      Arrays.sort(t);
      String k = String.valueOf(t);
      d.computeIfAbsent(k, key -> new ArrayList<>()).add(s);
    }
    return new ArrayList<>(d.values());
  }
}

class Solution {
public:
  vector<vector<string>> groupAnagrams(vector<string>& strs) {
    unordered_map<string, vector<string>> d;
    for (auto& s : strs) {
      string k = s;
      sort(k.begin(), k.end());
      d[k].emplace_back(s);
    }
    vector<vector<string>> ans;
    for (auto& [_, v] : d) ans.emplace_back(v);
    return ans;
  }
};

func groupAnagrams(strs []string) (ans [][]string) {
  d := map[string][]string{}
  for _, s := range strs {
    t := []byte(s)
    sort.Slice(t, func(i, j int) bool { return t[i] < t[j] })
    k := string(t)
    d[k] = append(d[k], s)
  }
  for _, v := range d {
    ans = append(ans, v)
  }
  return
}

function groupAnagrams(strs: string[]): string[][] {
  const d: Map<string, string[]> = new Map();
  for (const s of strs) {
    const k = s.split('').sort().join('');
    if (!d.has(k)) {
      d.set(k, []);
    }
    d.get(k)!.push(s);
  }
  return Array.from(d.values());
}

use std::collections::HashMap;

impl Solution {
  pub fn group_anagrams(strs: Vec<String>) -> Vec<Vec<String>> {
    let mut map = HashMap::new();
    for s in strs {
      let key = {
        let mut arr = s.chars().collect::<Vec<char>>();
        arr.sort();
        arr.iter().collect::<String>()
      };
      let val = map.entry(key).or_insert(vec![]);
      val.push(s);
    }
    map.into_iter()
      .map(|(_, v)| v)
      .collect()
  }
}

using System.Collections.Generic;

public class Comparer : IEqualityComparer<string>
{
  public bool Equals(string left, string right)
  {
    if (left.Length != right.Length) return false;

    var leftCount = new int[26];
    foreach (var ch in left)
    {
      ++leftCount[ch - 'a'];
    }

    var rightCount = new int[26];
    foreach (var ch in right)
    {
      var index = ch - 'a';
      if (++rightCount[index] > leftCount[index]) return false;
    }

    return true;
  }

  public int GetHashCode(string obj)
  {
    var hashCode = 0;
    for (int i = 0; i < obj.Length; ++i)
    {
      hashCode ^= 1 << (obj[i] - 'a');
    }
    return hashCode;
  }
}

public class Solution {
  public IList<IList<string>> GroupAnagrams(string[] strs) {
    var dict = new Dictionary<string, List<string>>(new Comparer());
    foreach (var str in strs)
    {
      List<string> list;
      if (!dict.TryGetValue(str, out list))
      {
        list = new List<string>();
        dict.Add(str, list);
      }
      list.Add(str);
    }
    foreach (var list in dict.Values)
    {
      list.Sort();
    }
    return new List<IList<string>>(dict.Values);
  }
}

方法二：计数

我们也可以将方法一中的排序部分改为计数，也就是说，将每个字符串 $s$ 中的字符以及出现的次数作为 key，将字符串 $s$ 作为 value 存入哈希表当中。

时间复杂度 $O(n\times (k + C))$。其中 $n$ 和 $k$ 分别是字符串数组的长度和字符串的最大长度，而 $C$ 是字符集的大小，本题中 $C = 26$。

class Solution:
  def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
    d = defaultdict(list)
    for s in strs:
      cnt = [0] * 26
      for c in s:
        cnt[ord(c) - ord('a')] += 1
      d[tuple(cnt)].append(s)
    return list(d.values())

class Solution {
  public List<List<String>> groupAnagrams(String[] strs) {
    Map<String, List<String>> d = new HashMap<>();
    for (String s : strs) {
      int[] cnt = new int[26];
      for (int i = 0; i < s.length(); ++i) {
        ++cnt[s.charAt(i) - 'a'];
      }
      StringBuilder sb = new StringBuilder();
      for (int i = 0; i < 26; ++i) {
        if (cnt[i] > 0) {
          sb.append((char) ('a' + i)).append(cnt[i]);
        }
      }
      String k = sb.toString();
      d.computeIfAbsent(k, key -> new ArrayList<>()).add(s);
    }
    return new ArrayList<>(d.values());
  }
}

class Solution {
public:
  vector<vector<string>> groupAnagrams(vector<string>& strs) {
    unordered_map<string, vector<string>> d;
    for (auto& s : strs) {
      int cnt[26] = {0};
      for (auto& c : s) ++cnt[c - 'a'];
      string k;
      for (int i = 0; i < 26; ++i) {
        if (cnt[i]) {
          k += 'a' + i;
          k += to_string(cnt[i]);
        }
      }
      d[k].emplace_back(s);
    }
    vector<vector<string>> ans;
    for (auto& [_, v] : d) ans.emplace_back(v);
    return ans;
  }
};

func groupAnagrams(strs []string) (ans [][]string) {
  d := map[[26]int][]string{}
  for _, s := range strs {
    cnt := [26]int{}
    for _, c := range s {
      cnt[c-'a']++
    }
    d[cnt] = append(d[cnt], s)
  }
  for _, v := range d {
    ans = append(ans, v)
  }
  return
}

function groupAnagrams(strs: string[]): string[][] {
  const map = new Map<string, string[]>();
  for (const str of strs) {
    const k = str.split('').sort().join('');
    map.set(k, (map.get(k) ?? []).concat([str]));
  }
  return [...map.values()];
}