Python solution with detailed explanation


  • 0
    G

    Solution

    Group Shifted Strings https://leetcode.com/problems/group-shifted-strings/

    Algorithm

    1. This problem is similar to grouping anagrams problem. We found a signature for anagrams and then added to hash table.
    2. The challenge here is to find a signature to identify shift sequences.
    3. Imagine all characters (a to z) in a circle. The sequence can thus be the differences between adjacent characters.
    4. How do you handle "az" and "ba"? Add 26 to Negative differences
    5. How do you handle "a", "z"? Represent by empty tuple.
    from collections import defaultdict
    class Solution(object):
        def get_sign(self, w):
            sign = []
            for i in range(1, len(w)):
                diff = ord(w[i])-ord(w[i-1])
                diff = diff if diff > 0 else diff + 26
                sign.append(str(diff))
            return tuple(sign)
        
        def groupStrings(self, strings):
            """
            :type strings: List[str]
            :rtype: List[List[str]]
            """
            groups = defaultdict(list)
            for w in strings:
                groups[self.get_sign(w)].append(w)
            return groups.values()
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.