Leetcode 249.Group Shifted Strings

[locked]

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:

1	"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:

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

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

So the thing is quite clear: for one char or only one word of the length, they are in the list. For others, get the differences of ord() to the first char, if it is negative, plus 26, then pick strings that have the same list of differences. For example, for "abc", "bcd" and "xyz", their difference lists should be [1,1]. Or we can use a string to replace the list.

# Time:  O(nlogn)
# Space: O(n)

class Solution:
    # @param {string[]} strings
    # @return {string[][]}
    def groupStrings(self, strings):
        groups = {};
        for s in strings:  # Grouping.
            if self.hashStr(s) not in groups:
                groups[self.hashStr(s)] = [s]
            else:
                groups[self.hashStr(s)].append(s)

        result = []
        for key, val in groups.iteritems():
            result.append(sorted(val))
        
        return result

    def hashStr(self, s):
        base = ord(s[0])
        hashcode = ""
        for i in xrange(len(s)):
            if ord(s[i]) - base >= 0:
                hashcode += unichr(ord('a') + ord(s[i]) - base)
            else:
                hashcode += unichr(ord('a') + ord(s[i]) - base + 26)
        return hashcode