> For the complete documentation index, see [llms.txt](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/string/249.-group-shifted-strings.md).

# 249. 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"]
]
```

{% hint style="info" %}
每組shift strings之間有個共同點就是每個string裡面的char跟第一個char的相對距離是一樣的，例如abc和efg是一組group shifted strings，b相對於a位移1，c相對a位移2，而f相對e位移1，g相對e位移2，所以他們的相對位移一樣，所以看作同一組shifted strings。
{% endhint %}

```cpp
vector<vector<string>> groupStrings(vector<string>& strings) { // time: O(n * str_len); space: O(n)
    unordered_map<string, vector<string> > m;
    for (string& str : strings) {
        string encode_key;
        for (char c : str) {
            encode_key += to_string((c - str[0] + 26) % 26) + ",";
        }
        m[encode_key].push_back(str);
    }
    vector<vector<string> > res;
    for (auto it = m.begin(); it != m.end(); ++it) {
        res.push_back(vector<string>(it->second.begin(), it->second.end()));
    }
    return res;
}
```