Group Shift String

题目描述

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"],

Return:

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

Note: For the return value, each inner list's elements must follow the lexicographic order.

解题方法

首先最明显的是按长度分，然后我们观察几组string的变化，可以发现同一组的string他们string之间的间隔是一样的，而如何记录每个字符之间的间隔并且保存下来呢，list是mutable的不行，我们可以采用string或者tuple的方式来保存为key.

Solution

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

        results = []
        dic = {}
        for s in strings:
            hs = self.strHash(s)
            if hs not in dic:
                dic[hs] = [s]
            else:
                dic[hs].append(s)

        for key in dic:
            ls = dic[key]
            ls.sort()
            results.append(ls)

        return results


    def strHash(self, s):
        hsList = [(ord(i) - ord(s[0])) % 26 for i in s]
        return tuple(hsList)

Reference

group shift string