首页 > 代码库 > Leetcode Anagrams

Leetcode Anagrams

2024-07-10 20:59:30   223人阅读

Given an array of strings, return all groups of strings that are anagrams.

Note: All inputs will be in lower-case.

题目的意思是：给出一组字符串，按组返回拥有相同变位词的字符串

解题思路是：

　　对单词中得字母排序，如果排序后的单词是一样的，那么我们可以判定这两个单词有相同的变位词。

  • 首先，求出每个单词的变位词，以变位词作为键插入哈希表中，值为一个链表。
  • 然后，把该单词附在这个链表末端。
  • 最后，遍历哈希表的值，输出长度大于1的字符串

 

class Solution {public:    vector<string> anagrams(vector<string> &strs){        unordered_map<string, vector<int> > hash_map;        for(int  i = 0 ; i < strs.size(); ++ i){            string s = strs[i];            sort(s.begin(),s.end());            if(hash_map.find(s) != hash_map.end()){                vector<int> a = hash_map[s];                a.push_back(i);                hash_map[s] = a;            }else{                vector<int> a;                a.push_back(i);                hash_map.insert(make_pair(s,a));            }        }        vector<string> res;        for(unordered_map<string,vector<int> >::iterator iter = hash_map.begin(); iter!= hash_map.end();++iter){            vector<int> a = iter->second;            if(a.size() > 1){                for(int i = 0 ; i < a.size(); ++ i){                    res.push_back(strs[a[i]]);                }            }        }        return res;    }};

 


联系
我们