Problem description:

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

Solution:

  1. Find a way to determine whether if two word are the same pattern. We can do it by checking the difference for each character in the word. This result can use as a key to store every word who has same pattern.
  2. Then we can use an unordered_map to store the key and value vector<string>, which is the words that have equal pattern.

For example:
for a string s of length n, we encode its shifting feature as “s[1] - s[0], s[2] - s[1], …, s[n - 1] - s[n - 2],”.
if we have abc and efg. We can find out that,
distance of a and b is 1, distance of b and c is 1.
distance of e and f is 1, distance of f and g is 1.
Therefore, these two words are the same pattern.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    vector<vector<string>> groupStrings(vector<string>& strings) {
        /*
        1. find out how to find the pattern for each words, we can calculate the diff between every word
        2. use the diff as key, the same words as value
        */
        unordered_map<string, vector<string>> map;
        for(auto s: strings)
            map[shift(s)].push_back(s);
        
        vector<vector<string>> res;
        for(auto s: map){
            res.push_back(s.second);
        }
        return res;
    }
    
    string shift(string input){
        string res;
        for(int i= 1; i< input.length(); i++){
            int diff= input[i]-input[i-1];
            res+= diff< 0 ? diff+26: diff;
            res+= ',';
        }
        return res;
    }
};

Solution2:

more concise code. add 26 to the diff and mod it afterward.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
vector<vector<string>> groupStrings(vector<string>& strings) {
    vector<vector<string> > res;
    unordered_map<string, vector<string>> map;
    for (auto a : strings) {
        string t = "";
        for (char c : a) {
            /*
            if((c-a[0]) < 0)
                t+= ((c-a[0]+26) + ',');
            else
                t+= ((c-a[0]) + ',');
                */
            
            t += (((c+ 26 - a[0]) % 26) + ',');
        }
        map[t].push_back(a);
    }
    
    for(auto m: map)
        res.push_back(m.second);

    return res;
  }
};

reference: