Question

剑指 Offer II 033. 变位词组

题目描述

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

注意：若两个字符串中每个字符出现的次数都相同且字符顺序不完全相同，则称它们互为变位词。

 

示例 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] 仅包含小写字母

 

注意：本题与主站 49 题相同： https://leetcode.cn/problems/group-anagrams/

解法

方法一：哈希表

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());
}

方法二：计数

我们也可以将方法一中的排序部分改为计数，也就是说，将每个字符串 $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()];
}