# 249. Group Shifted Strings

## Description

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.

## Solutions

The relative distance between each letter of the string and the first character is equal.

For example, abc and efg are mutually offset. For abc, the distance between b and a is 1, and the distance between c and a is 2. For efg, the distance between f and e is 1, and the distance between g and e is 2.

Let’s look at another example. The distance between az and yx, z and a is 25, and the distance between x and y is also 25 (direct subtraction is -1, which is the reason for adding 26 and taking the remainder).

Then, in this case, all strings that are offset from each other have a unique distance difference. According to this, the mapping can be well grouped.

• class Solution {
public List<List<String>> groupStrings(String[] strings) {
Map<String, List<String>> mp = new HashMap<>();
for (String s : strings) {
int diff = s.charAt(0) - 'a';
char[] t = s.toCharArray();
for (int i = 0; i < t.length; ++i) {
char d = (char) (t[i] - diff);
if (d < 'a') {
d += 26;
}
t[i] = d;
}
String key = new String(t);
}
return new ArrayList<>(mp.values());
}
}

• class Solution {
public:
vector<vector<string>> groupStrings(vector<string>& strings) {
unordered_map<string, vector<string>> mp;
for (auto& s : strings) {
int diff = s[0] - 'a';
string t = s;
for (int i = 0; i < t.size(); ++i) {
char d = t[i] - diff;
if (d < 'a') d += 26;
t[i] = d;
}
cout << t << endl;
mp[t].push_back(s);
}
vector<vector<string>> ans;
for (auto& e : mp)
ans.push_back(e.second);
return ans;
}
};

• '''
>>> a = defaultdict(list)
>>> b = defaultdict([])
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: first argument must be callable or None

>>> ord('c')
99
>>> ord('c') - ord('a')
2
>>> ord('d') - 2
98
>>> chr(98)
'b'

>>> a = {"s":1, "t":2, "x":3}
>>> a
{'s': 1, 't': 2, 'x': 3}
>>> a.items()
dict_items([('s', 1), ('t', 2), ('x', 3)])
>>> a.values()
dict_values([1, 2, 3])
>>> list(a.values())
[1, 2, 3]
'''

from collections import defaultdict

class Solution:
def groupStrings(self, strings: List[str]) -> List[List[str]]:
mp = defaultdict(list)
for s in strings:
t = []
diff = ord(s[0]) - ord('a')
for c in s:
d = ord(c) - diff
if d < ord('a'):
d += 26
t.append(chr(d))
k = ''.join(t)
mp[k].append(s)
return list(mp.values())


• func groupStrings(strings []string) [][]string {
mp := make(map[string][]string)
for _, s := range strings {
k := ""
for i := range s {
k += string((s[i]-s[0]+26)%26 + 'a')
}
mp[k] = append(mp[k], s)
}
var ans [][]string
for _, v := range mp {
ans = append(ans, v)
}
return ans
}