249. 移位字符串分组
前言
「力扣题解」系列致力于分享有价值的题目、探讨更优秀的解法。
这是本系列的第 1 篇题解，更多题解关注 Somnia1337@力扣。
哈希表，经典开局。
题目描述
难度：🟡中等
给定一个字符串，对该字符串可以进行“移位”的操作，也就是将字符串中每个字母都变为其在字母表中后续的字母，比如："abc"->"bcd"。这样，我们可以持续进行“移位”操作，从而生成如下移位序列：
"abc"->"bcd"->...->"xyz"
给定一个仅包含小写字母字符串的列表，将该列表中所有满足“移位”操作规律的组合进行分组并返回。
输入：["abc", "bcd", "acef", "xyz", "az", "ba", "a", "z"]
输出：
[
["abc","bcd","xyz"],
["az","ba"],
["acef"],
["a","z"]
]
解释：可以认为字母表首尾相接，所以 'z' 的后续为 'a'，所以 ["az","ba"] 也满足“移位”操作规律。题意理解
输入：String[]。
输出：List<List<String>>。
对输入的若干字符串进行分组，如果两个字符串 x、y 满足：
- 在一个无限循环的字母表（“ab..zab…“）中对
x平移，存在一个平移使x与y相同
那么 x、y 属于同一分组。
举例："aec"->"bfd"->"cge"，因此它们均属于同一分组。
解题思路
如果可以对字符串计算一种值，该值能够作为每个分组的字符串的特征值（同一分组的字符串算得的值相同，不同分组的则不同），那么可以根据该值进行分组。
不难联想到，哈希值符合此要求。
自定义一个哈希函数，对于输入数组中的每个字符串 s，计算其特征串 key，再用一张哈希表记录分组，以 key 为键，以同组字符串列表为值。
那么，这个哈希函数怎么写呢？
将字符串首字符平移到 'a'、后续字符平移相同距离，得到一个新串。观察同组字符串经该变换得到的新串：
"bed" 与 "hkj" 同组
将 "bed" 平移到以 'a' 开头
'b' - 1 = 'a'，后续字符也减1
'e' - 1 = 'd'
'd' - 1 = 'c'
新串 "adc"
将 "hkj" 平移到以 'a' 开头
'h' - 7 = 'a'，后续字符也减7
'k' - 7 = 'd'
'j' - 7 = 'c'
新串 "adc"发现同组字符串经变换得到的新串相同，由此写出哈希函数：
将 s 中的每个字符 s[i] 替换为 'a'+(s[i]-offset)%26。
其中 offset = s[0]-'a'，即首字符与 'a' 的距离。字母表是无限循环的，因此对 26 取余。
复杂度
- 时间复杂度：。
- 空间复杂度：。
代码
Java
class Solution {
public List<List<String>> groupStrings(String[] strings) {
Map<String, List<String>> groups = new HashMap<>(); // 记录分组
for (String s : strings) {
String key = hash(s); // 将哈希串作为键
List<String> group = groups.getOrDefault(key, new ArrayList<>());
group.add(s); // 在对应分组中添加s
groups.put(key, group);
}
return new ArrayList<>(groups.values());
}
// 对字符串计算哈希串
public String hash(String s) {
StringBuilder key = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
// 平移每一位上的字符，构造哈希串
key.append('a' + (s.charAt(i) - (s.charAt(0) - 'a')) % 26);
}
return key.toString();
}
}Python
class Solution:
def groupStrings(self, strings: List[str]) -> List[List[str]]:
# 对字符串计算哈希串
def hash(s) -> str:
key = ""
offset = ord(s[0]) - ord("a")
# 平移每一位上的字符，构造哈希串
for c in s:
key += chr(ord("a") + (ord(c) - ord("a") - offset) % 26)
return key
ans = defaultdict(list) # 记录分组
for s in strings:
ans[hash(s)].append(s) # 将哈希串作为键，在对应分组中添加s
return list(ans.values())相关题目
49. 字母异位词分组
最后
更多系列「外源推文」&「生活分享」关注公众号：