LeetCode 249 Group Shifted Strings

LeetCode

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.

题目大意：

将单词按等偏移量分组

解题思路：

单词分组题，设计一个id。组内的每个单词里字母之间的差值是一致的，如abd, wxz, 差值分别为1和2，这是同一组。

解题步骤：

N/A

注意事项：

求每个单词每个字母之间的差值，用下滑线连接作为id。注意差值可能为负数，所以要取mod变正
单一字母单词，不存在偏移量，id为空，所以代码不需要特殊处理

Python代码：

def groupStrings(self, strings: List[str]) -> List[List[str]]:
	res = collections.defaultdict(list)
	for s in strings:
		_id = ''
		for j in range(1, len(s)):
			_id += str((ord(s[j]) - ord(s[j - 1])) % 26) + '_'
		res[_id].append(s)
	return list(res.values())

算法分析：

时间复杂度为O(nm)，空间复杂度O(1), n为单词个数, m为单词最长长度。