[LeetCode] [编程珠玑:变位词]Anagrams - c++编程基础

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

Note: All inputs will be in lower-case.

问题描述：给定一列字符串，返回所有的变位词组合。

首先，要解释一下变位词。

变位词：两个单词包含的字母是相同的，只是顺序不一样，比如abc与bca就互为变位词。

这里的解法分为两步：

（1）建立一个multimap，遍历所有单词，当取得一个单词时，将它排序后，以排序后的字符串为键，排序前的字符串为值插入到multimap中，同时将键保存在set中。

（2）遍历键的集合set，当取一个键时，计算它在multimap出现的次数，如果次数小于等于1（当然，次数不可能小于1），说明只有一个单词对应该键，就什么也不干，如果次数大于1，就获得这个键在multimap中的起始和结束位置，将值插入到结果vector中。

class Solution {  
public:  
    vector anagrams(vector &strs) {  
        // IMPORTANT: Please reset any member data you declared, as  
        // the same Solution instance will be reused for each test case.  
        if(strs.size() <= 1)  
            return vector




();  
          
        multimap records;  
        set sset;  
        string tmp;  
  
        for(vector::iterator iter = strs.begin();  
                                     iter != strs.end(); ++iter) {  
            tmp = *iter;  
            sort(tmp.begin(), tmp.end());  
            records.insert(make_pair(tmp, *iter));  
            sset.insert(tmp);  
        }  
  
        vector svec;  
        pair::iterator, multimap::iterator> loc;  
        for(set::iterator iter = sset.begin();  
                                  iter != sset.end(); ++iter) {  
            if(records.count(*iter) > 1) {  
                loc = records.equal_range(*iter);  
                for(multimap::iterator iter = loc.first;  
                                                       iter != loc.second; ++iter) {  
                    svec.push_back((*iter).second);                                             
                }  
            }  
        }  
  
        return svec;  
    }  
};