249. Group Shifted Strings

• Difficulty: Medium

• Topics: Hash Table, String

• Similar Questions:

  • Group Anagrams

Problem:

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

Solutions:

class Solution {
public:
    vector<vector<string>> groupStrings(vector<string>& strings) {
        unordered_map<string, vector<string>> groups;
        for (auto& s : strings) {
            string shift = s;
            int diff = s[0] - 'a';
            for (int i = 0; i < shift.length(); ++i) {
                shift[i] -= diff;
                if (shift[i] < 'a') {
                    shift[i] += 26;
                }
            }
            groups[shift].push_back(s);
        }
        vector<vector<string>> ret;
        for (auto& entry : groups) {
            ret.push_back(entry.second);
        }
        return ret;
    }
};