[leetcode] Anagrams


Anagrams

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

Note: All inputs will be in lower-case.

anagrams变位词。

如:eat和tea,字母相同,只是排列顺序不同。

思路,用hashtable,先对string中的字母进行排序,这样所有的变位词都会变得相同。在hashtable中为一个入口,再利用unordered_map<string, MyStr>进行构建,需要注意,如果是第一次遇见相同的变位词的话,需要把当前str和在hashtable中的str都压入结果vector中。

class MyStr{
public:
  string str;
  bool isVisited;
  MyStr(string s, bool a):str(s),isVisited(a){}
  MyStr(){}
};
class Solution {
public:
    vector<string> anagrams(vector<string> &strs) {
        unordered_map<string, MyStr> h;
        vector<string> re;
        for(vector<string>::iterator it = strs.begin(); it != strs.end(); it++){
            string s = *it;
            sort(s.begin(), s.end());
            if(h.find(s) == h.end()){//not found
                h[s] = MyStr(*it, false);
            }
            else if (h[s].isVisited == false){// first found
                re.push_back(h[s].str);
                re.push_back(*it);
                h[s].isVisited = true;
            }
            else{//not first found
                re.push_back(*it);
            }
        }
        return re;
    }
};

Untitled

Leave a comment

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.