249. Group Shifted Strings (M)

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 non-empty 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"]
]

我的答案：比较简单的一道题，题目第一部分description没讲清楚的是，xyz后面还有yza，这个在example里面会出现。然后难点在如何让xyz和yza有同样的一个计算结果0 1 2，yza是24 25 0，计算差值之后是0 1 -24。如果每个字母都有2种可能都需要考虑，指数爆炸了，必须只能有单一的hash tag。

class Solution {
public:
    vector<vector<string>> groupStrings(vector<string>& strings) {
        vector<vector<string>> ans;
        unordered_map<string, int> seq2index;
        
        string s_back;
        for (auto& s:strings) { //edge case: len=0
            s_back = ShiftBack(s);
            if (seq2index.find(s_back) == seq2index.end()) {
                ans.push_back({s});
                seq2index[s_back] = ans.size()-1;
            }
            else {
                ans[seq2index[s_back]].push_back(s);
            }
        }
        
        return ans;
    }
    // abc xyz yza zab 25 0 1 -> 0 -25 -24 -> 0 1 2
    // ba zy az
    // cab -> 2 0 1 -> 0 -2 -1 -> 0 24 25 zxy ayz bza -> 1 25 0 -> 0 25 -1
    string ShiftBack(string& s) {
        char start = s[0];
        int len = s.size();
        string s_back(len, 'a');
        for (int i=0; i<len; ++i) {
            int diff = s[i]-start;
            if (diff < 0)
                diff += 26;
            s_back[i] += diff;
        }
        
        return s_back;
    }
};

Runtime: 4 ms, faster than 94.10% of C++ online submissions for Group Shifted Strings.
Memory Usage: 8.2 MB, less than 84.55% of C++ online submissions for Group Shifted Strings.