字母异位词分组

Tips

题目类型: HashMap

题目

给你一个字符串数组, 请你将字母异位词组合在一起. 可以按任意顺序返回结果列表. 字母异位词是由重新排列源单词的字母得到的一个新单词, 所有源单词中的字母通常恰好只用一次, 本题均为小写字母.

提示:

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

示例

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

输出: [['bat'], ['nat', 'tan'], ['ate', 'eat', 'tea']]

输入: strs = ['']

输出: [['']]

输入: strs = ['a']

输出: [['a']]

题解

思路比较简单, 对于异位词, 它们字母的组成是固定的, 比如 abc, bac, cba 都是由 a, b, c 三个字母组成的. 因此可以将它们按字母顺序重新排列, 得到的都是 abc, 便用来当做哈希表的 key, 那么相同 key 的单词放到一个数组里即可.

JavaScript

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function (strs) {
  const map = new Map()

  for (const str of strs) {
    const orderStr = str.split('').sort().join()

    if (map.has(orderStr)) {
      map.set(orderStr, [...map.get(orderStr), str])
    } else {
      map.set(orderStr, [str])
    }
  }

  return [...map.values()]
}

Rust

use std::collections::HashMap;

pub fn group_anagrams(strs: Vec<String>) -> Vec<Vec<String>> {
    let mut map: HashMap<String, Vec<String>> = HashMap::new();

    for str in strs {
        let mut order_vec = str.chars().collect::<Vec<char>>();
        order_vec.sort();
        let order_str = order_vec.iter().collect::<String>();

        map.entry(order_str).or_insert(Vec::new()).push(str);
    }

    map.values().cloned().collect()
}