思路:利用unordered_mapunordered_set

  • 前者保存根据字母排序后的单词以及对应的原始单词
  • 如果某一个原始单词已经插入结果,那么将其记录在unordered_set,防止重复插入

代码如下:

//
// Created by jt on 2020/9/29.
//
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <string>
using namespace std;

class Solution {
public:
    vector<string> anagrams(vector<string> &strs) {
        unordered_map<string, string> mp;
        unordered_set<string> added;
        vector<string> res;
        for (string str : strs) {
            string tmp = str;
            sort(tmp.begin(), tmp.end());
            if (mp.count(tmp)) {
                if (added.count(tmp) == 0) {
                    // 防止重复插入第一个换位词
                    res.push_back(mp[tmp]);
                    added.insert(tmp);
                }
                res.push_back(str);
            } else {
                mp[tmp] = str;
            }
        }
        return res;
    }
};