leetcode
leetcode 201 ~ 250
移位字符串分组

移位字符串分组

难度:

标签:

题目描述

代码结果

运行时间: 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的方式,这样做的目的是什么?是否为了处理字母表环绕的情况?
采用取模26的方式主要是为了处理字母表环绕的情况。例如,从 'z' 转到 'a' 应当被视为一个合法的移位操作。ASCII码直接相减会得到-25,而取模26后,这个转换正确地映射为1,即'z'到'a'视为向前移动了1位。这样做确保了所有的字符转换都可以在26个字母的循环中正确表达,不受字母表顺序的限制。
🦆
特征字符串计算中,为什么选择将差值用逗号分隔拼接而不是直接拼接或使用其他分隔符?这样做有什么优势或特别的考虑?
将差值用逗号分隔拼接而不是直接拼接的主要原因是为了避免相邻差值的数字合并导致歧义。例如,差值序列'12'和'3'如果直接拼接会变成'123',这与差值序列'1'和'23'直接拼接同样会形成'123',从而无法区分这两种不同的特征字符串。使用逗号分隔可以清晰地区分每一对字符之间的差值,确保每个差值都被正确识别和处理。
🦆
为何单个字符的字符串返回空字符串作为其特征字符串?这样做对分组有什么影响?
单个字符的字符串返回空字符串作为其特征字符串是因为单字符之间没有相邻的字符,因此不存在可计算的ASCII码差值。将这类字符串的特征字符串设为空字符串意味着所有单字符字符串都会被归入同一组,这样做简化了处理单字符情形的逻辑,并保持了算法的一致性。
🦆
哈希表group_dict的键是特征字符串,如果有多个不同的字符串具有相同的特征字符串,它们是否一定是同一组移位字符串?能否给出一个具体的例子说明?
如果多个不同的字符串具有相同的特征字符串,它们一定是同一组移位字符串。例如,字符串'abc'和'def'具有相同的特征字符串,因为从'a'到'b'、'b'到'c'的差值和从'd'到'e'、'e'到'f'的差值都是1。这表明每个字符都是按相同的方式移位的。因此,具有相同特征字符串的字符串组被视为移位字符串的相同组。

相关问题

字母异位词分组

给你一个字符串数组,请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

 

示例 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] 仅包含小写字母