题目描述

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.

样例

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

算法1

(哈希表) $O(n)$

观察规律可得需要同组的string必然可以从a开始的string转化而来，所以遍历所有string s并且将s转化为a开头的string base。用哈希表维护所有已知的base完成遍历。

C++ 代码

class Solution {
private:
    string translate(string& s)
    {
        string a;
        char ci = s[0];
        int base = ci - 'a';

        for (char c : s)
        {
            int i = ((c - 'a') + 26 - base) % 26;
            a += ('a' + i);
        }

        return a;
    }

public:
    vector<vector<string>> groupStrings(vector<string>& strings) {
        unordered_map<string, vector<string>> hash;

        for (auto& s : strings)
        {
            string base = translate(s);
            if (hash.count(base) > 0)
            {
                hash[base].push_back(s);
            }
            else
            {
                vector<string> g;
                g.push_back(s);
                hash[base] = g;
            }
        }

        vector<vector<string>> ans;
        for (auto& [k, v] : hash)
        {
            ans.push_back(v);
        }

        return ans;
    }
};