49. Group Anagrams

Given an array of strings, group anagrams together.

For example, given: ["eat", "tea", "tan", "ate", "nat", "bat"],
Return:

[
["ate", "eat","tea"],
["nat","tan"],
["bat"]
]
Note: All inputs will be in lower-case

S: hashmap + sort

    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> map;
        vector<vector<string>> result;
        for(auto s: strs){
            string str = s;
            sort(str.begin(), str.end());
            if(map.find(str) != map.end()) map[str].push_back(s);
            else map[str] = vector<string>(1, s);
        }
        for(const auto &i: map){
            result.push_back(i.second);
        }
        return result;
    }

242. Valid Anagram

Given two strings s and t, write a function to determine if t is an anagram of s.

For example,
s = "anagram", t = "nagaram", return true.
s = "rat", t = "car", return false.

Note:
You may assume the string contains only lowercase alphabets.

Follow up:
What if the inputs contain unicode characters? How would you adapt your solution to such case?

Show Company Tags
Show Tags
Show Similar Problems

S：count

因为只有26个小写字母，可用一个数组记录每个字母出现的次数，在s中出现加一，在t中出现减一，最后数组元素都为零返回true反之返回false。如果string中的元素不止26个可用hashmap记录

    bool isAnagram(string s, string t) {
        vector<int> count(26, 0);
        for(auto i: s) count[i-'a']++;
        for(auto i: t) count[i-'a']--;
        for(auto i: count) if(i != 0) return false;
        return true;
    }

249. Group Shifted Strings

Given a string, we can "shift" each of its letter to its successive letter, for example: "abc" -> "bcd". We can keep "shifting" which forms the sequence:

"abc" -> "bcd" -> ... -> "xyz"
Given a list of strings which contains only lowercase alphabets, group all strings that belong to the same shifting sequence.

For example, given: ["abc", "bcd", "acef", "xyz", "az", "ba", "a", "z"],
A solution is:

[
["abc","bcd","xyz"],
["az","ba"],
["acef"],
["a","z"]
]

S1：brutal force O(k*n^2)

a..z形成了一个环如何解决：当t[i] - s[i] < 0时 +26得到正向结果

    vector<vector<string>> groupStrings(vector<string>& strings) {
        vector<vector<string>> result;
        for(auto & s : strings){
            bool find = false;
            for(auto & strs: result){
                if(isSamePattern(s, strs[0])){
                    strs.push_back(s);
                    find = true;
                    break;
                }
            }
            if(!find) result.push_back(vector<string>{s});
        }
        return result;
    }

    bool isSamePattern(string &s, string &t){
        if(s.size()!=t.size()) return false;
        if(s.size()==1) return true;
        int dist = (t[0]-s[0]<0)? 26+(t[0]-s[0]) : t[0]-s[0];
        for(int i = 1; i<s.size(); ++i)
        {
            int a = (t[i]-s[i]<0)? 26+(t[i]-s[i]) : t[i]-s[i];
            if(a!=dist) return false;
        }
        return true;   
    }

S2： hashmap encodeing O(k*n)

关键是如何encoding shifted string让他们有相同的key，这里采用相邻两char的差值组成的string为key

    vector<vector<string>> groupStrings(vector<string>& strings) {
        vector<vector<string>> result;
        unordered_map<string, vector<string>> map;
        for (const string& s : strings) {
            string key = encode(s);
            if (map.find(key) != map.end()) {
                map[key].push_back(s);
            } else map[key] = vector<string>{s};
        }
        for (const auto& i : map) {
            result.push_back(i.second);
        }
        return result;
    }

    string encode(string s) {
        string result = "";
        for (int i = 1; i < s.size(); ++i) {
            int gap = s[i] - s[i - 1];
            if (gap < 0) gap += 26;
            result += ('a' + gap);
        }
        return result;
    }