leetcode-49

LeetCode 49. 字母异位词分组

• 1 题目描述
• 2 思路(超时)
• 3 改进
• 4 Notes

1 题目描述

• 题目链接：49. 字母异位词分组

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

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

示例1:

输入： strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出： [[“bat”],[“nat”,”tan”],[“ate”,”eat”,”tea”]]

示例2:

输入： strs = [“”]
输出： [[“”]]

示例3:

输入： strs = [“a”]
输出： [[“a”]]

2 思路（超时）

• 先遍历一遍字符串数组，用一个数组 vector<int> cnt(26); 记录每个字符串中各个个字母出现的次数，以 当前字符串的索引为 key 、cnt 为 value 、 插入到 map 中, map 定义为：map<vector<int>, int>;

for(int i = 0; i < strs.size(); i++){   //遍历数组
    for(char ch: strs[i]){
        cnt[ch - 'a']++;                //得到字符串中每个字母的数量
    }  
    m[i] = cnt;     //以索引i为key,cnt为value插入map中
    fill(cnt.begin(), cnt.end(), 0);    //将cnt清零
}

• 两重for遍历字符串数组，遇到值一样的就将对应的strs插入到一个暂存结果的vector<string> group中，并将所对应的键从 map 中erase 掉. 内循环结束后把暂存结果的 group 插入答案中

for(int i = 0; i < strs.size(); i++){
    if(!m.count(i)) continue;       //内循环中i已经插入到答案中且被erase了
    for(int j = i+1; j < strs.size(); j++){
        if(m.count(j) && m[i] == m[j]){
            group.push_back(strs[j]);
            m.erase(j);
        }
    }
    group.push_back(strs[i]);
    m.erase(i);         //完成插入，erase掉
    res.push_back(group);
    group.clear();
}

完整的代码如下：

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> res;
        vector<string> group;
        vector<int> cnt(26);
        map<int, vector<int>> m;
        for(int i = 0; i < strs.size(); i++){
            for(char ch: strs[i]){
                cnt[ch - 'a']++;
            }
            m[i] = cnt;
            fill(cnt.begin(), cnt.end(), 0);
        }
        for(int i = 0; i < strs.size(); i++){
            if(!m.count(i)) continue;
            for(int j = i+1; j < strs.size(); j++){
                if(m.count(j) && m[i] == m[j]){
                    group.push_back(strs[j]);
                    m.erase(j);
                }
            }
            group.push_back(strs[i]);
            m.erase(i);
            res.push_back(group);
            group.clear();
            
        }
        return res;
    }
};

提交发现超时了，主要是因为两层for循环导致复杂度过高

3 改进

  上面的思路将索引作为 key, 导致查找的时候需要对字符串逐一遍历、两两进行值的比较，相等了再插入到答案中，但这种方法其实无异于暴力求解。
  进行优化，类似的思路:

• 采用 cnt 数组作为 key ，value 则定义为vector<string>, 即 map 定义为：map<vector<int>, vector<string>> m;.
• 每次统计字符串中的各个字母次数，然后将当前遍历的字符串存到map中，即 m[cnt].push_back(strs[i]).
• 通过迭代器对 map 进行遍历，并将 map 中的 value 一一插入到答案中.

完整代码如下：

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> res;
        vector<int> cnt(26);
        map<vector<int>, vector<string>> m;
        for(int i = 0; i < strs.size(); i++){
            for(char ch: strs[i]){
                cnt[ch - 'a']++;
            }
            m[cnt].emplace_back(strs[i]);
            fill(cnt.begin(), cnt.end(), 0);
        }
        for(auto iter: m){                      //iter.first指向map中的key
            res.emplace_back(iter.second);      //iter.second指向map中的value
        }
        return res;
    }
};

4 Notes

1. emplace_back() 和 push_back() 的区别

• push_back() 的调用过程：先会调用构造函数构造临时对象，然后调用拷贝构造函数将这个临时对象放入容器中。原来的临时变量释放。这样造成的问题就是临时变量申请资源的浪费。

• emplace_back() 在插入的时候原地构造，不需要触发拷贝构造和转移构造。

  注意：1. 不能向 emplace_back() 传递引用.
     2. 不应该直接传递原 vector 的迭代器，即 vec.emplace_back(vec.back()) 是不正确的，因为插入需要重新分配内存，会导致迭代器的失效，应该先定义一个变量存放 vec.back(),再把这个变量传递给emplace_back().

1. 对于 map 容器，用迭代器对 map 进行遍历，迭代器有两个成员， first 指向当前遍历元素的 key ， second 指向当前的 value.

map<string, int> m;
m["one"] = 1;

map<string, int>::iterator p = m.begin();
p->first; // 这个是  string  值是 "one"
p->second; //这个是 int 值是 1

1. vector 的清零操作是 fill(vec.begin(), vec.end(), 0); 而不是 vec.clear();， 后者是将 vector 清空，即相当于内存释放.