LeetCode 面试金典 17.25「单词矩阵」实战：等长分组 + 回溯 + 字典树剪枝的困难题解法-平芜编程栈

示例工程
教程

【免费下载链接】leetcode

🔥LeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer（第 2 版）》、《程序员面试金典（第 6 版）》题解

本文围绕《程序员面试金典（第 6 版）》面试题 17.25（Word Rectangle / 单词矩阵，困难）展开，讲解如何在一个最多 1000 个单词的清单中，构建「每一行、每一列都构成词典单词」的面积最大的字母矩形。读完本文，你将掌握：按词长分组压缩搜索空间、用字典树（Trie）对列方向做前缀剪枝、用两条面积/行数剪枝控制回溯规模的完整技巧，并可以对照仓库中 Python、Java、C++、Go、Swift 五种语言的参考实现进行复现。

题目：构建面积最大的「单词矩阵」

给定一份单词的清单，设计一个算法，创建由字母组成的面积最大的矩形，满足：

每一行自左向右组成一个单词；
每一列自上而下也组成一个单词；
不要求这些单词在清单里连续出现，但要求所有行等长、所有列等高；
如果有多个面积最大的矩形，输出任意一个均可；
一个单词可以重复使用。

示例 1：

输入: ["this", "real", "hard", "trh", "hea", "iar", "sld"] 输出: [ "this", "real", "hard" ]

示例 2：

输入: ["aa"] 输出: ["aa", "aa"]

约束条件（原题说明）：

约束	含义
`words.length <= 1000`	单词总数最多 1000 个
`words[i].length <= 100`	单个单词长度最多 100
数据保证单词足够随机	题目性质保证了剪枝搜索在实践中可行

题目的英文版本见 README_EN.md，中文版见 README.md，题目在 LCCI 总目录中登记为困难难度，可参考 lcci 题目列表。

为什么朴素穷举不可行

最直接的想法是枚举行数的选择、再逐行选词拼矩形。但一旦行数或词长较大，组合空间是指数级的：1000 个单词中选若干行、每行再各自选词，搜索树会迅速膨胀。而本题存在两个可利用的结构性质，这正是参考解法（文档中称为「分组 + 回溯 + 字典树」）的全部出发点：

同一矩形的所有行长度必然相同——因此不同长度的单词永远不会出现在同一个矩形里，可以按长度把问题拆成若干互不相干的子问题；
列也必须是词典中的词——这意味着矩阵「长高」时列方向的前缀必须始终合法，可以用字典树在回溯过程中实时检验并提前剪枝，而不必等到矩阵拼完才做整体校验。

思路一：按词长分组，拆分子问题

构建单词矩阵时所用的单词长度是相同的，因此先将所有单词按长度分组，记录在哈希表d中（键为词长，值为该长度的单词列表），同时把每个单词插入字典树、记录最长词长max_l。对每个长度分组独立做一次回溯即可，搜索空间被大幅压缩：

d = defaultdict(list) trie = Trie() max_l = 0 for w in words: trie.insert(w) max_l = max(max_l, len(w)) d[len(w)].append(w)

这一步同时完成了三件事：分组（缩小候选集）、建字典树（供列方向校验）、求出max_l（后续剪枝的上界）。

思路二：check 函数——沿字典树逐列判定的三态结果

判断当前已构建的矩阵是否「仍然有希望」时，不需要等矩阵完成。把所有单词插入同一棵字典树后，对矩阵的每一列，从树根开始自上而下逐字符走：

走到某一步发现子节点不存在：这一列的前缀都不是词典中任何单词的前缀，矩阵彻底无望，返回状态0（不可行，立即剪枝）；
走完所有行且落在单词结尾节点（is_end为真）：这一列本身就是一个完整单词；若所有列都如此，返回状态1（当前矩阵已是合法单词矩阵，可以更新答案）；
走完所有行但没有落在单词结尾：这些列目前只是某些词典单词的前缀，随着矩阵继续加高仍有可能变成完整单词，返回状态2（暂不可判定，可以继续扩展）。

对应 Python 实现（与 Solution.py 中check闭包一致）：

def check(mat): m, n = len(mat), len(mat[0]) ans = 1 for j in range(n): node = trie for i in range(m): idx = ord(mat[i][j]) - ord("a") if node.children[idx] is None: return 0 node = node.children[idx] if not node.is_end: ans = 2 return ans

三态语义可以整理为一张表：

返回值	语义	回溯策略
`0`	某列连前缀都不存在	弹出当前行，换下一个候选词
`1`	所有列都是完整单词	更新最大面积与答案，然后继续尝试加行
`2`	所有列都只是前缀	不更新答案，但允许继续加行扩展

每次check的代价是对每列做一次字典树行走，即与当前矩阵规模m × n线性相关，常数很小，这使得「每加一行就检查一次」在经济上完全可行。

思路三：回溯构建矩阵与两条剪枝

用列表t记录当前已构建的行（每个元素是一个单词，彼此等长）。从某个长度分组ws出发：取出一个单词w追加到t末尾，调用check(t)；若返回0则回退并尝试下一个单词；若返回1且面积超过已知最优，则记录答案；随后递归继续加行，最后把w从t中移除进入下一轮搜索。

dfs入口处有两条关键剪枝（对应 Solution.py 第 34 行）：

if len(ws[0]) * max_l <= max_s or len(t) >= max_l: return

面积上界剪枝：本分组的词长为len(ws[0])，矩阵行数最多为max_l（见下一条），因此该分组能产生的面积上界是len(ws[0]) * max_l。若这个上界都不超过已找到的最大面积max_s，整个分组无需再搜；
行数上界剪枝：列方向由len(t)个字符拼成，任何词典单词长度不超过max_l，因此行数达到max_l后无法再合法加高，立即停止。

此外，回溯循环中不对已选单词做去重——这正是题目「一个单词可以重复使用」的体现：示例 2 中只有["aa"]一个词，答案["aa", "aa"]就是同一单词选了两行。

完整实现（Python 3）

下面是参考文档中的完整解法（与仓库 Solution.py 一致，Trie节点固定 26 个小写字母分支）：

class Trie: def __init__(self): self.children = [None] * 26 self.is_end = False def insert(self, w): node = self for c in w: idx = ord(c) - ord("a") if node.children[idx] is None: node.children[idx] = Trie() node = node.children[idx] node.is_end = True class Solution: def maxRectangle(self, words: List[str]) -> List[str]: def check(mat): m, n = len(mat), len(mat[0]) ans = 1 for j in range(n): node = trie for i in range(m): idx = ord(mat[i][j]) - ord("a") if node.children[idx] is None: return 0 node = node.children[idx] if not node.is_end: ans = 2 return ans def dfs(ws): nonlocal ans, max_s, max_l if len(ws[0]) * max_l <= max_s or len(t) >= max_l: return for w in ws: t.append(w) st = check(t) if st == 0: t.pop() continue if st == 1 and max_s < len(t) * len(t[0]): ans = t[:] max_s = len(t) * len(t[0]) dfs(ws) t.pop() d = defaultdict(list) trie = Trie() max_l = 0 for w in words: trie.insert(w) max_l = max(max_l, len(w)) d[len(w)].append(w) max_s = 0 ans = [] for ws in d.values(): t = [] dfs(ws) return ans

几个容易踩坑的实现细节：

更新答案时必须拷贝当前矩阵（ans = t[:]），因为t是共享的回溯状态，后续pop会改变其内容；
状态2（只是前缀）不能剪枝，只有状态0才意味着彻底无望；
dfs返回后必须把t恢复原状（pop），保证兄弟分支看到一致的搜索状态。

Java 实现要点

Java 参考实现（见 Solution.java）把maxL、maxS、ans、trie、t提升为Solution的成员变量，以闭包方式改写为实例方法：

class Solution { private int maxL; private int maxS; private String[] ans; private Trie trie = new Trie(); private List<String> t = new ArrayList<>(); public String[] maxRectangle(String[] words) { Map<Integer, List<String>> d = new HashMap<>(100); for (String w : words) { maxL = Math.max(maxL, w.length()); trie.insert(w); d.computeIfAbsent(w.length(), k -> new ArrayList<>()).add(w); } for (List<String> ws : d.values()) { t.clear(); dfs(ws); } return ans; } private void dfs(List<String> ws) { if (ws.get(0).length() * maxL <= maxS || t.size() >= maxL) { return; } for (String w : ws) { t.add(w); int st = check(t); if (st == 0) { t.remove(t.size() - 1); continue; } if (st == 1 && maxS < t.size() * t.get(0).length()) { maxS = t.size() * t.get(0).length(); ans = t.toArray(new String[0]); } dfs(ws); t.remove(t.size() - 1); } } private int check(List<String> mat) { int m = mat.size(), n = mat.get(0).length(); int ans = 1; for (int j = 0; j < n; ++j) { Trie node = trie; for (int i = 0; i < m; ++i) { int idx = mat.get(i).charAt(j) - 'a'; if (node.children[idx] == null) { return 0; } node = node.children[idx]; } if (!node.isEnd) { ans = 2; } } return ans; } }

注意ans的更新用t.toArray(new String[0])完成快照，check中每列独立从trie根节点重新出发——列与列之间没有共享路径，不能复用上一列的终点节点。

示例 1 逐步推演

以["this", "real", "hard", "trh", "hea", "iar", "sld"]为例：

按长度分组后，4 词长分组为["this", "real", "hard"]，3 词长分组为["trh", "hea", "iar", "sld"]；
在 4 词长分组中，回溯依次放入this、real、hard。此时矩阵为 3×4：

t h i s r e a l h a r d

三列分别为tih、rea、sal。在只放了前两行时，check会对每列沿字典树下行；当三行齐备后，若列串恰好是词典单词则返回1，否则返回2（仍可加高）。参考输出[this, real, hard]面积 12；

搜索中任何一列若中途走出字典树（状态0），该分支立刻被剪掉，避免继续盲目加行。

仓库中的多语言参考实现

本题在仓库中提供了 5 种语言的独立实现文件，核心逻辑（分组、check三态、两条剪枝）完全一致，只在语言惯用法上略有差异，可对照阅读：

语言	文件	实现特点
Python 3	Solution.py	以闭包`check`/`dfs`嵌套在`maxRectangle`内，`nonlocal`共享答案状态
Java	Solution.java	状态量提升为成员变量，`dfs`/`check`为实例方法
C++	Solution.cpp	`check`与`dfs`用`std::function`lambda 承载，字典树节点动态分配
Go	Solution.go	`dfs`用自引用变量递归；回退行用切片截断`t = t[:len(t)-1]`
Swift	Solution.swift	用`switch st`分别处理三种状态，`case 0`只回退不递归

从源码结构看，五个实现中剪枝条件、状态语义、答案更新时机完全同构，这为跨语言复现提供了很好的互校基准。

小结

面试题 17.25 是一道典型的「结构性剪枝」困难题，解法可以概括为三个正交的技巧：

按词长分组：利用「矩形各行等长」的必然性，把一个大搜索空间拆成若干独立子问题；
字典树列方向校验：check的0 / 1 / 2三态设计让剪枝与「矩阵已完成」的判定复用同一次行走，代价与当前矩阵规模线性相关；
面积与行数双上界剪枝：len(ws[0]) * max_l <= max_s与len(t) >= max_l两条条件把回溯树的有效深度锁死在最长词长之内。

配合题目「单词足够随机」的数据保证，这套组合在实际输入上能够把指数级搜索压缩到可行规模。若想继续深入，建议直接阅读 Solution.py 与 Solution.java 的逐行实现，并手推示例 1 的完整搜索树，体会状态2（前缀合法但非单词）在剪枝决策中的关键作用。