Leetcode 249: Group Shifted String

https://leetcode.com › problems › 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"],
Return:

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

Note: For the return value, each inner list's elements must follow the lexicographic order.

Notes:

This question is not hard to come up a solution, but it seems not easy to make the code clean.

Below is one way to code. Basically, if two strings belong to the same group, the difference of between all the letters and the first letter are the same for both strings. So we use this as a key to a hash table.

See the code below:

class Solution {
public:
    vector<vector<string>> groupStrings(vector<string>& strings) {
        vector<vector<string>> res;
        unordered_map<string, multiset<string>> m;
        for (auto a : strings) {
            string s = "";
            for (char &c : a) {
                s += to_string((c + 26 - a[0]) % 26) + ",";
            }
            m[s].insert(a);
        }
        for(auto it = m.begin(); it != m.end(); ++it) {
            res.push_back(vector<string>(it->second.begin(), it->second.end()));
        }
        return res;
    }
};