249.Group Shifted Strings

Tags: Hash Table String Medium

Links: https://leetcode-cn.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.

Example:

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

---

class Solution {
public:
    vector<vector<string>> groupStrings(vector<string>& strings) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        unordered_map<int, vector<string>> um;
        int n = strings.size();
        for (int i = 0; i < n; ++i) {
            int len = strings[i].size();
            um[len].push_back(strings[i]);
        }

        vector<vector<string>> res;
        for (auto & e : um) {
            //字符串长度为1或者只有一个元素
            if (e.first == 1 || e.second.size() == 1) {
                res.push_back(e.second);
                continue;
            }

            auto &v = e.second;
            unordered_map<string, vector<string>> tmp;
            int len = v[0].size();
            string count(len, ' ');

            for (const auto & word : v) {
                int gap = word[0] - 'a';
                count[0] = 'a';
                for (int i = 1; i < len; ++i) {
                    count[i] = 'a' + ((word[i] - 'a') - gap + 26) % 26;
                }
                tmp[count].push_back(word);
            }

            for (auto & ele : tmp) {
                res.push_back(ele.second);
            }
        }

        return res;
    }
};

满足移位操作的必须字符串的长度相同，所以首先应该进行字符串分组。上面这种思路其实还是有点麻烦了，考虑满足移位的规律：

abc bcd xyz

也就是长度相同的字符串的对应位，偏移量是相同的，比如bcd的每个字符相对于abc都偏移了1，xyz相对abc偏移了23，所以恰好可以用abc作为键，只要偏移化简后和abc相同，那么就可以归为一组。