# Question

Formatted question description: https://leetcode.ca/all/249.html

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.

# Algorithm

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.

# Code

• import java.util.*;

public class Group_Shifted_Strings {
class Solution {
public List<List<String>> groupStrings(String[] strings) {

List<List<String>> result = new ArrayList<>();

if (strings == null || strings.length == 0) {
return result;
}

Map<String, List<String>> map = new HashMap<>();

for (String str : strings) {
String key = findKey(str);
if (map.containsKey(key)) {
} else {
List<String> list = new ArrayList<>();
map.put(key, list);
}
}

// iterate the map

return result;
}

private String findKey(String str) {
// @note: should check for empty string
if (str.length() == 0) {
return "";
}

StringBuilder sb = new StringBuilder();

int distance = str.charAt(0) - 'a'; // @note: key is shifting word to start with 'a'

for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
char offset = (char) (c - distance);
if (offset < 'a') {
offset = (char) (offset + 26);
}
sb.append(offset);
}

return sb.toString();
}
}
}

############

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 - '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) - 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())

############

class Solution(object):
def groupStrings(self, strings):
"""
:type strings: List[str]
:rtype: List[List[str]]
"""
d = {}
ans = []
single = []
for s in strings:
if len(s) == 1:
single.append(s)
continue
hashcodeArray = []
pre = ord(s) - ord("a")
for i in range(1, len(s)):
hashcodeArray.append(str(((ord(s[i]) - ord("a")) - pre) % 26))
pre = ord(s[i]) - ord("a")
hashcode = ",".join(hashcodeArray)
if hashcode not in d:
d[hashcode] = [s]
else:
d[hashcode].append(s)
for k in d:
ans.append(d[k])
if single:
ans.append(single)
return ans


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