249.Group Shifted Strings

Tags: [string], [pattern], [char], [map]

Com: {g}

Link: https://leetcode.com/problems/group-shifted-strings/\#/description

Given a string, we can "shift" each of its letter to its successive letter, for example:"abc" -> "bcd". We can keep "shifting" which forms the sequence:

"abc" -> "bcd" -> ... -> "xyz"

Given a list of strings which contains only lowercase alphabets, group all strings that belong to the same shifting sequence.

For example, given:["abc", "bcd", "acef", "xyz", "az", "ba", "a", "z"],
A solution is:

[
  ["abc","bcd","xyz"],
  ["az","ba"],
  ["acef"],
  ["a","z"]
]

Solution: Map

class Solution(object):
    def groupStrings(self, strings):
        """
        :type strings: List[str]
        :rtype: List[List[str]]
        """
        if not strings:
            return []

        patterns_to_strs = collections.defaultdict(list)
        for s in strings:
            p = self.get_pattern(s)
            patterns_to_strs[p].append(s)

        return patterns_to_strs.values()

    def get_pattern(self, s):
        if not s:
            return ''

        chars = list(s)

        # make the last char to 'z'.
        diff = ord('z') - ord(s[-1])
        if not diff:
            return s

        for i in xrange(len(chars)):
            chars[i] = chr(ord('a') + (ord(chars[i]) - ord('a') + diff) % 26)

        return ''.join(chars)

Revelation:

• When we calculate the pattern for the given string, we make the last char be 'z'. The reason we cannot stop once we meet 'z' is because there exists the case 'az', 'ba'.
• Be careful of the line: 'chars[i] = chr(ord('a') + (ord(chars[i]) - ord('a') + diff) % 26)'.

Note:

• Time complexity = O(n*k), n is the number of elements in the given array, k is the max length of strings in the given array.