字母异位词分组

Category	Difficulty	Likes	Dislikes
algorithms	Medium (67.20%)	1117	-

Tags

hash-table | string

Companies

amazon | bloomberg | facebook | uber | yelp

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

字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。

示例 1:

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

示例 2:

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

示例 3:

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

提示：

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

Discussion | Solution

解法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    /**
    * ## 解题思路
    * * hashmap
    * 1. 遍历strs，使用hashmap来记录遍历中遇到的每个str；
    * 2. hashmap的key为sort(str), val为[str]；
    * 3. 遍历完strs后，遍历hashmap,获取所有的val；
    */
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> m;

        // 统计各个string 排序后的 map
        for(auto str: strs) {
            string s = str;
            sort(s.begin(), s.end());
            m[s].push_back(str);
        }

        vector<vector<string>> res;
        for(auto mi: m) {
            res.push_back(mi.second);
        }
        return res;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
// @lc code=start
impl Solution {
    /// ## 解题思路
    /// - hashmap
    /// 1. 将每个字符串排序;
    /// 2. 已排序后的字符串作为key, 将每个字符串放入string->vec<string> hashmap中;
    /// 3. hashmap中的values即为结果;
    pub fn group_anagrams(strs: Vec<String>) -> Vec<Vec<String>> {
        use std::collections::HashMap;
        let mut hashmap: HashMap<String, Vec<String>> = HashMap::new();
        for str in strs {
            let mut s = str.as_bytes().to_vec();
            s.sort();
            hashmap
                .entry(String::from_utf8(s).unwrap())
                .or_default()
                .push(str.clone());
        }
        hashmap.into_values().collect()
    }
}
// @lc code=end

字母异位词分组

字母异位词分组

解法

相关文章：