移位字符串分组
难度:
标签:
题目描述
代码结果
运行时间: 22 ms, 内存: 16.1 MB
/*
* Leetcode 249: Group Shifted Strings using Java Streams
* This solution leverages Java Streams for a more concise approach.
*/
import java.util.*;
import java.util.stream.Collectors;
public class SolutionStream {
public List<List<String>> groupStrings(String[] strings) {
return new ArrayList<>(
Arrays.stream(strings)
.collect(Collectors.groupingBy(this::getShiftKey))
.values()
);
}
private String getShiftKey(String str) {
StringBuilder key = new StringBuilder();
for (int i = 1; i < str.length(); i++) {
int diff = str.charAt(i) - str.charAt(i - 1);
if (diff < 0) {
diff += 26;
}
key.append(diff).append(',');
}
return key.toString();
}
public static void main(String[] args) {
SolutionStream sol = new SolutionStream();
String[] strings = {"abc", "bcd", "acef", "xyz", "az", "ba", "a", "z"};
List<List<String>> result = sol.groupStrings(strings);
System.out.println(result);
}
}
解释
方法:
该题解的思路是将每个字符串映射为一个特征字符串,使得属于同一组的字符串有相同的特征字符串。具体做法是,对于每个字符串,计算相邻字符的ASCII码差值并取模26,然后将差值按顺序拼接成一个字符串作为该字符串的特征字符串。最后使用哈希表将具有相同特征字符串的字符串分组。
时间复杂度:
O(n*m)
空间复杂度:
O(n+m)
代码细节讲解
🦆
在计算字符ASCII码差值时采用取模26的方式,这样做的目的是什么?是否为了处理字母表环绕的情况?
▷🦆
特征字符串计算中,为什么选择将差值用逗号分隔拼接而不是直接拼接或使用其他分隔符?这样做有什么优势或特别的考虑?
▷🦆
为何单个字符的字符串返回空字符串作为其特征字符串?这样做对分组有什么影响?
▷🦆
哈希表group_dict的键是特征字符串,如果有多个不同的字符串具有相同的特征字符串,它们是否一定是同一组移位字符串?能否给出一个具体的例子说明?
▷相关问题
字母异位词分组
给你一个字符串数组,请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
示例 1:
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
示例 2:
输入: strs = [""]
输出: [[""]]
示例 3:
输入: strs = ["a"]
输出: [["a"]]
提示:
1 <= strs.length <= 104
0 <= strs[i].length <= 100
strs[i]
仅包含小写字母