249

249. Group Shifted Strings (Medium)

We can shift a string by shifting each of its letters to its successive letter.

• For example, "abc" can be shifted to be "bcd".

We can keep shifting the string to form a sequence.

• For example, we can keep shifting "abc" to form the sequence: "abc" -> "bcd" -> ... -> "xyz".

Given an array of strings strings, group all strings[i] that belong to the same shifting sequence. You may return the answer in any order.

 

Example 1:

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

Example 2:

Input: strings = ["a"]
Output: [["a"]]

 

Constraints:

• 1 <= strings.length <= 200
• 1 <= strings[i].length <= 50
• strings[i] consists of lowercase English letters.

Companies:
Facebook, Google

Related Topics:
Array, Hash Table, String

Similar Questions:

• Group Anagrams (Medium)

Solution 1.

// OJ: https://leetcode.com/problems/group-shifted-strings/
// Author: github.com/lzl124631x
// Time: O(S) where S is size of all the contents in `strings`.
// Space: O(K) where K is the length of output array.
class Solution {
public:
    vector<vector<string>> groupStrings(vector<string>& A) {
        unordered_map<string, int> m;
        vector<vector<string>> ans;
        for (auto &s : A) {
            int diff = s[0] - 'a';
            auto key = s;
            for (char &c : key) c = 'a' + (c - 'a' - diff + 26) % 26;
            if (!m.count(key)) {
                m[key] = ans.size();
                ans.emplace_back();
            }
            ans[m[key]].push_back(s);
        }
        return ans;
    }
};
};