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.

Example:

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

每組shift strings之間有個共同點就是每個string裡面的char跟第一個char的相對距離是一樣的，例如abc和efg是一組group shifted strings，b相對於a位移1，c相對a位移2，而f相對e位移1，g相對e位移2，所以他們的相對位移一樣，所以看作同一組shifted strings。

vector<vector<string>> groupStrings(vector<string>& strings) { // time: O(n * str_len); space: O(n)
    unordered_map<string, vector<string> > m;
    for (string& str : strings) {
        string encode_key;
        for (char c : str) {
            encode_key += to_string((c - str[0] + 26) % 26) + ",";
        }
        m[encode_key].push_back(str);
    }
    vector<vector<string> > res;
    for (auto it = m.begin(); it != m.end(); ++it) {
        res.push_back(vector<string>(it->second.begin(), it->second.end()));
    }
    return res;
}