法算day2

字母异位词分组

问题描述

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

示例 1:
输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出: [[“bat”],[“nat”,”tan”],[“ate”,”eat”,”tea”]]

解释：
在 strs 中没有字符串可以通过重新排列来形成 “bat”。
字符串 “nat” 和 “tan” 是字母异位词，因为它们可以重新排列以形成彼此。
字符串 “ate” ，”eat” 和 “tea” 是字母异位词，因为它们可以重新排列以形成彼此。

示例 2:
输入: strs = [“”]
输出: [[“”]]

示例 3:
输入: strs = [“a”]
输出: [[“a”]]

提示：
1 <= strs.length <= 104
0 <= strs[i].length <= 100
strs[i] 仅包含小写字母

java版

方法一：排序签名，即对字符排序

import java.util.*;

/**
 * 主类：GroupAnagrams
 * 功能：把一堆字符串中所有“字母异位词”自动归到同一组。
 * 字母异位词：字母相同、出现次数相同，只是顺序不同，如 "eat" 和 "tea"。
 */
public class GroupAnagrams {

    /**
     * 唯一公开接口：groupAnagrams
     * 参数：strs – 待分组的原始字符串数组，可能为空、可能含空串
     * 返回：List<List<String>> – 每一层 List 就是一个分组，组内字符串互为异位词
     */
    public List<List<String>> groupAnagrams(String[] strs) {
        /* ---------- 1. 边界保护 ---------- */
        if (strs == null || strs.length == 0) {
            // 外面传进来的是空指针或空数组，直接返回“空列表”，避免后面代码抛异常
            return new ArrayList<>();
        }

        /* ---------- 2. 准备哈希表 ---------- */
        // key（String）：某个“签名”，所有互为异位词的字符串都会生成完全相同的签名
        // value（List<String>）：属于这个签名的所有原始字符串
        Map<String, List<String>> map = new HashMap<>();

        /* ---------- 3. 遍历每个字符串 ---------- */
        for (String s : strs) {                 // s 可能是 ""，也可能是 "aabbCc" 等任意小写字母
            /* 3.1 生成签名：把字符排序后得到的字符串就是签名
               原因：异位词排序后必然得到同一串字符，例如 "eat"、"tea" 排序后都是 "aet" */
            char[] chars = s.toCharArray();     // 把当前字符串拆成字符数组，方便排序
            Arrays.sort(chars);                 // 快速排序，复杂度 O(k log k)，k 为字符串长度
            String key = new String(chars);     // 再把排好序的字符数组拼回字符串，得到签名

            /* 3.2 把原始字符串挂到对应签名下面
               computeIfAbsent 的意思是：如果 map 里还没有这个签名，就新建一个空 ArrayList 并返回；
               如果已经有，就直接返回原来的 List。无论哪种情况，add(s) 都会把当前字符串放进这个 List */
            map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
        }

        /* ---------- 4. 组装最终结果 ---------- */
        // map.values() 拿到所有分组 List，再套一层 ArrayList 就是题目要的返回格式
        return new ArrayList<>(map.values());
    }

    /* ---------- 5. 简单自测 ---------- */
    public static void main(String[] args) {
        GroupAnagrams solution = new GroupAnagrams();
        String[] strs = {"eat", "tea", "tan", "ate", "nat", "bat"};
        // 期望输出：[[eat, tea, ate], [tan, nat], [bat]]（顺序可能不同）
        System.out.println(solution.groupAnagrams(strs));
    }
}

✅ 说明：
算法复杂度
时间：O(n·k log k)，n 为字符串个数，k 为字符串最大长度（排序耗时）。
空间：O(n·k)，用于存储 map 与结果。

代码疑惑点答疑

疑点一

public List<List<String>> groupAnagrams(String[] strs) 这一长串看起来吓人，其实每个关键字都在“报户口”——告诉你 谁都能调用、给的是字符串数组、还回来的是两层口袋的字符串。一句话拆 6 段解释：

1. public
   “大家都能用”。换成 private 就只能类内部自己玩，别人调不到。

2. List<List<String>>
   返回类型：两层 List 嵌套。

   • 外层 List 的每一项代表 一个分组；
   • 内层 List<String> 装的是 该分组里的所有字符串。
     为什么用接口 List 而不用具体类？
     面向接口编程：调用者只关心“它是个列表”，不关心你背后是 ArrayList 还是 LinkedList，给实现留余地。

3. groupAnagrams
   方法名，见名知意：把 anagrams（字母异位词）group（分组）。

4. (String[] strs)
   形参：一个字符串数组，里面扔进来一堆原始单词，等待被分类。

5. 为什么没有 static？
   需要 先 new 一个对象 再调用，这样方法内部可以访问到对象级别的字段（虽然现在没用，但预留扩展）。如果写成 static，就成了工具方法，属于类本身，无法访问实例成员。

6. 为什么泛型要写两次 <String>？
   Java 泛型不支持“裸”嵌套，必须写全。List<List<String>> 读作：一个列表，里面的元素还是“装字符串的列表”。

总结：
这句声明就是一份 方法招牌——“公开营业，收字符串数组，返分组列表，欢迎来调”。

疑点二

return new ArrayList<>(); 这一行干的事情可以拆成三步看：

1. new ArrayList<>()
   在堆上真正创建了一个 空的 ArrayList 对象（底层数组长度默认 0，第一次 add 时才会扩容）。

2. 泛型推断
   因为方法返回值已经被编译器确定为 List<List<String>>，所以这里的 <> 被自动推断成 ArrayList<List<String>>()；你不用重复写泛型参数。

3. return 出去
   你拿到手的 实际上 是一个：

   • 空的、
   • 可变的、
   • 顺序保持的、
   • 允许重复元素的
     ArrayList 实例，只不过对外展现的类型是它的接口 List<List<String>>。

一句话：
“别人眼里你只是‘空列表’，本质上就是刚出炉、还没装任何分组的 ArrayList 对象。”

疑点三

for (String s : strs) 是 Java 的“增强版 for 循环”（也叫 foreach），它把“索引、边界判断、自增”这些脏活全部藏起来，让你只关心 每个元素本身。
逐字拆解：
for (
循环关键字，开场白。
String s
循环变量：每次进入循环体，都会把当前拿到的字符串塞进这个局部变量 s 里，类型必须和数组元素一致（这里是 String）。
:
读作“在……里面”，官方叫“in”。
strs
要被遍历的 数组或 Iterable 集合，这里是我们传进来的 String[] strs。
执行流程（伪代码等价）：

for (int i = 0; i < strs.length; i++) {
    String s = strs[i];   // 自动帮你取下标、赋值
    // ↓ 你自己的代码
    ...                   // 这里写对 s 的操作
}

索引 i 由编译器自动生成，但你 看不见、也用不到。
特点
只能 从前到后 一趟扫，不能跳着走，也不能反向。
不能修改数组长度（不能 add/remove），但 可以读取、可以修改元素本身（如果元素是可变对象）。
代码更短，少了下标越界风险，可读性高。
在本例里：
每轮循环 s 依次代表 “eat”、”tea”、”tan”……直到最后一个单词，循环自动结束。
你只需要把注意力放在“拿到一个字符串后怎么生成签名、怎么塞进 map”即可，下标那些事编译器全包。

疑点四

把这一行拆成“两句话”看，就秒懂：
map.computeIfAbsent(key, k -> new ArrayList<>())
意思是：
“如果 map 里还没有这个 key，就新建一个 空 ArrayList 并放进 map，然后把这个 List 返回；
如果已经存在，就直接把原来那个 List 返回。”
.add(s)
拿到上一步返回的 List（不管是刚新建的还是原来就有的），把当前字符串 s 塞进去。
所以整行等价于：

List<String> list = map.get(key);     // 先查
if (list == null) {                   // 没有就建
    list = new ArrayList<>();
    map.put(key, list);
}
list.add(s);                          // 再装

只是 computeIfAbsent 把“查-判-建-放”四步一次性做完，并直接返回那个 一定存在的 List，让你立刻能 .add(s)。
变量名 k 是 Lambda 的形参，代表 key，这里没用到，起个占位符名字即可。

重点理解

下面用一个完整的字符串当例子，把
map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
的每一步都“慢放”给你看。

假设当前字符串 s = “tea”

1. 生成签名
   char[] chars = “tea”.toCharArray() → 排序 → {‘a’,’e’,’t’} → key = “aet”

2. 看 map 里有没有 key=”aet”
   此时 map 还是空的，get(“aet”) 会返回 null。

3. 进入 computeIfAbsent
   因为找不到，于是执行 Lambda：k -> new ArrayList<>()
   新建一个空 ArrayList，把它放进 map，并把这个 List 返回。
   此刻内存里变成：
   map = {“aet” → []} （空列表）

4. 返回的 List 立刻 .add(s)
   [].add(“tea”) → 列表变成 [“tea”]
   最终 map 是：
   {“aet” → [“tea”]}

5. 下一个循环如果碰到 “eat”
   签名还是 “aet”，这次 map 里已存在，computeIfAbsent 直接返回原列表 [“tea”]，
   再 .add(“eat”) → 列表变成 [“tea”, “eat”]，无需再建 ArrayList。

一句话：
“第一次来就给你新建个口袋，后面再来同名签名直接往旧口袋里继续扔。”

python版

from collections import defaultdict  # 引入一个方便的字典类，后面会解释
from typing import List              # 只是告诉 Python 我们要用 List 做类型提示，不写也能跑

class Solution:                      # 把所有功能包在一个类里，刷题平台喜欢这种写法
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        # 1. 建一个“有默认值”的字典：当访问一个不存在的 key 时，它会自动先放一个空列表进去
        groups = defaultdict(list)

        # 2. 逐个看输入的字符串
        for s in strs:
            # 3. 把字符串里的字母按字母表顺序排好，变成“签名”
            #    例如 "tea" -> 排序后变成 "aet"
            key = ''.join(sorted(s))

            # 4. 把原字符串挂到这个签名对应的列表里
            #    同一签名下的所有字符串互为字母异位词
            groups[key].append(s)

        # 5. 把字典里所有的列表一次性拿出来，就是最终答案
        return list(groups.values())


# 下面这段是“自测”代码，只在直接运行本文件时生效
if __name__ == "__main__":
    print(Solution().groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"]))
    # 期望输出: [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]