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 <= 2001 <= strings[i].length <= 50strings[i]consists of lowercase English letters.
class Solution:
def groupStrings(self, strings: List[str]) -> List[List[str]]:
def shift_letter(letter, shift):
return chr( (ord(letter)-shift) % 26 + ord('a') )
def get_hash(string):
shift = ord(string[0])
return "".join( shift_letter(s, shift) for s in string)
d = collections.defaultdict(list)
for item in strings:
h = get_hash(item)
d[h].append(item)
return d.values()