难度: Medium
Submission
运行时间: 22 ms
内存: 16.1 MB
from collections import defaultdict
class Solution:
def word_to_number(self, word):
res = ''
if len(word) == 1:
return ''
for i in range(len(word) - 1):
num = (ord(word[i + 1]) - ord(word[i]))%26
res += ',' + str(num)
return res
def groupStrings(self, strings: list[str]) -> list[list[str]]:
group_dict = defaultdict(list)
for word in strings:
group_dict[self.word_to_number(word)].append(word)
return list(group_dict.values())
Explain
该题解的思路是将每个字符串映射为一个特征字符串，使得属于同一组的字符串有相同的特征字符串。具体做法是，对于每个字符串，计算相邻字符的ASCII码差值并取模26，然后将差值按顺序拼接成一个字符串作为该字符串的特征字符串。最后使用哈希表将具有相同特征字符串的字符串分组。
时间复杂度: O(n*m)
空间复杂度: O(n+m)
from collections import defaultdict
class Solution:
def word_to_number(self, word):
res = ''
if len(word) == 1:
return ''
for i in range(len(word) - 1):
# 计算相邻字符的ASCII码差值并取模26
num = (ord(word[i + 1]) - ord(word[i]))%26
res += ',' + str(num)
return res
def groupStrings(self, strings: list[str]) -> list[list[str]]:
group_dict = defaultdict(list)
for word in strings:
# 将每个字符串映射为特征字符串，并按特征字符串分组
group_dict[self.word_to_number(word)].append(word)
# 返回分组结果的列表
return list(group_dict.values())
Explore
采用取模26的方式主要是为了处理字母表环绕的情况。例如，从 'z' 转到 'a' 应当被视为一个合法的移位操作。ASCII码直接相减会得到-25，而取模26后，这个转换正确地映射为1，即'z'到'a'视为向前移动了1位。这样做确保了所有的字符转换都可以在26个字母的循环中正确表达，不受字母表顺序的限制。
将差值用逗号分隔拼接而不是直接拼接的主要原因是为了避免相邻差值的数字合并导致歧义。例如，差值序列'12'和'3'如果直接拼接会变成'123'，这与差值序列'1'和'23'直接拼接同样会形成'123'，从而无法区分这两种不同的特征字符串。使用逗号分隔可以清晰地区分每一对字符之间的差值，确保每个差值都被正确识别和处理。
单个字符的字符串返回空字符串作为其特征字符串是因为单字符之间没有相邻的字符，因此不存在可计算的ASCII码差值。将这类字符串的特征字符串设为空字符串意味着所有单字符字符串都会被归入同一组，这样做简化了处理单字符情形的逻辑，并保持了算法的一致性。
如果多个不同的字符串具有相同的特征字符串，它们一定是同一组移位字符串。例如，字符串'abc'和'def'具有相同的特征字符串，因为从'a'到'b'、'b'到'c'的差值和从'd'到'e'、'e'到'f'的差值都是1。这表明每个字符都是按相同的方式移位的。因此，具有相同特征字符串的字符串组被视为移位字符串的相同组。