249. Group Shifted Strings

Description

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

Discussion

The key is to find a representation of a pattern for each string, and use it as a key to do mapping.

Method 1

unordered_map<key, index of rst>

class Solution {
public:
    vector<vector<string>> groupStrings(vector<string>& strings) {
        vector<vector<string>> rst;

        if(0 == strings.size()) {
            return rst;
        }

        unordered_map<string, int> tracker;
        for(auto &word : strings) {
            string key = "0";
            for(int loop = 1; loop < word.size(); ++loop) {
                int distance = word[loop] - word[loop - 1];
                distance = (distance < 0) ? 26 + distance : distance;
                key+=to_string(distance);
            }

            if(tracker.find(key) != tracker.end()) {
                rst[tracker[key]].push_back(word);
            }
            else {
                rst.push_back(vector<string>());
                tracker[key] = rst.size() - 1;
                rst[rst.size() - 1].push_back(word);
            }
        }

        return rst;
    }
};

Method 2

unordered_map<key, vector<string>>