249. Group Shifted Strings

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 <= 200
  • 1 <= strings[i].length <= 50
  • strings[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()

Random Note


Best Django REST Framework Views Series Part 1 Part 2 Part 3