每日算法之三十八：Anagrams

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

Note: All inputs will be in lower-case.

回文字符串是指： 兩個字符串的字符個數完全相同，這兩個字符串是Anagrams。因此Anagrams至少指倆字符串。找出字符集合中的Anagrams組。

由此我們可以想到，只要將幾個單詞按照字母順序進行排序，就可以通過比較判斷他們是否是anagrams。

思路：用map記錄排序後的字符串以及首次出現的位置。

1. 從strs的第一個元素開始遍歷，首先對元素進行排序得到s；

2. 在map裡查找s；

3. 若不存在，將s以及該元素的下標存入map；

4. 若存在，首先將第一次出現s時的原始字符串存入結果res，即strs[map[s]]，並將map[s]設置為-1（防止下次再存），再將該字符串本身存入結果res；

5. 重復以上1-4步，直到遍歷結束。

下面是代碼：

class Solution {
public:
    vector anagrams(vector &strs) {
        vector res;//作為最後的結果集返回
        if(strs.size()<=1)//只有一個是不能夠成為回文字符串集的
            return res;
        map anagram;//暫存排序之後的字符串，同時還有存儲在strs中的位置
        for(int i = 0;i=0)//排序之前的s沒有被存儲在res中，因此要存儲，並且把標記為置為-1
                {
                    res.push_back(strs[anagram[s]]);
                    anagram[s] = -1;
                }
                res.push_back(strs[i]);//只要是在緩存中匹配的，就說明之前有匹配的回文串，添加到結果集中
            }
        }
        return res;
    }
};