Leetcode: Anagrams

前言:

做到Anagrams这道题, 费了半天劲没明白输入输出要求到底是怎样的。 最后找了两个测试用例终于明白题目要求了。

Input:  ["tea","and","ate","eat","den"]

Output:     ["tea","ate","eat"]

Input:       ["cat","rye","aye","dog", "god","cud","cat","old","fop","bra"]

Output:    ["cat","cat","dog","god"]

题目:

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

Note: All inputs will be in lower-case.

https://oj.leetcode.com/problems/anagrams/

分析:

Anagram可以知道Anagram什么意思, 

要点有两个:

        1. 把每个字符串排序后再处理, 可以判断是否是anagram

        2. 把处理好的数据放到map中, 供下次查询

        3. 注意anagram可能会出现三个一组的

代码:

class Solution
{
public:
    vector<string> anagrams(vector<string> &strs)
    {   
        vector<string> res;
        map<string, int> anagram;

        for (int i = 0; i < strs.size(); i++)
        {
            string s = strs[i];

            sort(s.begin(), s.end());
            if (anagram.find(s) == anagram.end())
                anagram[s] = i;
            else
            {
                //如果是第二个anagram
                if (anagram[s] > -1) 
                {
                    res.push_back(strs[anagram[s]]);
                    anagram[s] = -1; 
                }
                res.push_back(strs[i]);
            }
        }

        return res;
    }   
};

参考:

https://oj.leetcode.com/discuss/215/does-return-groups-return-result-vector-string-return-groups

http://www.cnblogs.com/AnnieKim/archive/2013/04/25/3041982.html

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/38756403