Anagrams

题目：

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

Example
Given ["lint", "intl", "inlt", "code"], return ["lint", "inlt", "intl"].
Given ["ab", "ba", "cd", "dc", "e"], return ["ab", "ba", "cd", "dc"].

分析：

有几处可以优化的地方

1. 词长度不会超过18
2. 每一次做for的时候都要check visited
3. 每一次可以先查词的size是否相等

解法：

class Solution {
public:    
    /**
     * @param strs: A list of strings
     * @return: A list of strings
     */
    bool isAnagrams(string a, string b) {
        if (a.size() != b.size() ) {
            return false;
        }
        vector<int> hash(26, 0);
        for (int i = 0; i < a.size(); i++) {
            hash[a[i] - 'a']++;
            hash[b[i] - 'a']--;
        }
        for (int i = 0; i < hash.size(); i++) {
            if (hash[i] != 0) {
                return false;
            }
        }
        return true;
    } 

    void findAnagrams(vector<string> &strs, int i, vector<string> &res, vector<bool> &visited) {
        if (visited[i]) {
            return;
        }
        if (strs[i].size() > 18) {
            return;
        }
        visited[i] = true;
        string word = strs[i];
        bool firstAnag = true;
        for (int j = i + 1; j < strs.size(); j++) {
            if (visited[j]) {
                continue;
            }
            if (strs[j].size() != word.size() ) {
                continue;
            }
            if (isAnagrams(word, strs[j]) ) {
                if (firstAnag) {
                    res.push_back(word);
                    firstAnag = false;
                }
                res.push_back(strs[j]);
                visited[j] = true;
            }
        }

    } 

    vector<string> anagrams(vector<string> &strs) {
        // write your code here
        vector<bool> visited(strs.size(), false);
        vector<string> res;
        for (int i = 0; i < strs.size(); i++) {
            if (visited[i]) {
                continue;
            }
            findAnagrams(strs, i, res, visited);
        }
        return res;
    }
};