LeetCode 面试题 17.25. 单词矩阵
目录
题目描述
题意分析
从单词表中构造面积最大的字符矩形：每一行自左向右是表中单词，每一列自上而下也必须是表中单词。行等长、列等高，单词允许按题意重复使用。
若矩形有 r 行、c 列，那么行单词长度必须是 c，列单词长度必须是 r。尺寸选择与内容搜索相互独立，先按长度分组能快速排除词表中不存在的维度。
逐行回溯时，已经形成的每一列虽然还不是完整单词，但必须是某个长度为 r 的单词前缀；否则无论后面补什么行都不可能成功。这是最关键的剪枝。
解法：长度分组 + 列前缀剪枝回溯
核心思路
预处理三类数据：长度到单词列表、长度到完整单词集合、长度到所有前缀集合。
对候选尺寸
r×c，只从长度 c 的单词中选行。加入一行后，构造当前 c 个列前缀，并确认它们都存在于“长度 r 的单词前缀集合”。深度达到 r 时，再确认每列都是完整单词。回溯不变量是：rectangle 中所有行长度为 c，且每个已形成列串都是某个长度 r 单词的前缀。它保证当前部分解仍有完成矩形的可能。
尺寸列表按长度降序枚举，并维护 bestArea。若
c×maxLength <= bestArea，后续更小 c 不可能改善；固定 c 时若r×c <= bestArea，后续更小 r 也可以停止。例：词表包含
["this","real","hard","trh","hea","iar","sld"]。选择 3 行、4 列：加入 "this" 后列前缀是 t/h/i/s；加入 "real" 后是 tr/he/ia/sl；加入 "hard" 后四列成为 trh/hea/iar/sld，全部在词表中，得到面积 12 的矩形。
解题步骤
- 按单词长度建立列表、完整集合和前缀集合。
- 取所有存在的长度并降序排列。
- 枚举行宽 c 与行数 r，跳过面积不可能超过当前最优的尺寸。
- 清空当前 rectangle，从长度 c 的行单词列表开始回溯。
- 每加入一行，检查 c 个列前缀是否都属于长度 r 的前缀集合。
- 深度达到 r 时检查所有列是否为完整单词；成功则保存矩形并更新 bestArea。
- 搜完所有仍可能改进的尺寸后返回答案。
代码实现
class Solution {
private Map<Integer, List<String>> wordsByLength;
private Map<Integer, Set<String>> wordSetByLength;
private Map<Integer, Set<String>> prefixSetByLength;
private List<String> rectangle;
private String[] answer;
public String[] maxRectangle(String[] words) {
buildWordData(words);
List<Integer> lengths = new ArrayList<>(wordsByLength.keySet());
lengths.sort((first, second) -> second - first);
answer = new String[0];
int bestArea = 0;
int maxLength = lengths.isEmpty() ? 0 : lengths.get(0);
for (int cols : lengths) {
if (cols * maxLength <= bestArea) {
break;
}
List<String> rowWords = wordsByLength.get(cols);
for (int rows : lengths) {
int area = rows * cols;
if (area <= bestArea) {
break;
}
if (!wordSetByLength.containsKey(rows)) {
continue;
}
rectangle = new ArrayList<>();
if (backtrack(rowWords, rows, cols)) {
bestArea = area;
answer = rectangle.toArray(new String[0]);
break;
}
}
}
return answer;
}
private void buildWordData(String[] words) {
wordsByLength = new HashMap<>();
wordSetByLength = new HashMap<>();
prefixSetByLength = new HashMap<>();
for (String word : words) {
int length = word.length();
wordsByLength.computeIfAbsent(length, key -> new ArrayList<>()).add(word);
wordSetByLength.computeIfAbsent(length, key -> new HashSet<>()).add(word);
Set<String> prefixes = prefixSetByLength.computeIfAbsent(length, key -> new HashSet<>());
for (int end = 1; end <= length; end++) {
prefixes.add(word.substring(0, end));
}
}
}
private boolean backtrack(List<String> rowWords, int rows, int cols) {
if (rectangle.size() == rows) {
return allColumnsAreWords(rows, cols);
}
for (String word : rowWords) {
rectangle.add(word);
if (allColumnPrefixesExist(rows, cols) && backtrack(rowWords, rows, cols)) {
return true;
}
rectangle.remove(rectangle.size() - 1);
}
return false;
}
private boolean allColumnPrefixesExist(int rows, int cols) {
Set<String> prefixes = prefixSetByLength.get(rows);
for (int col = 0; col < cols; col++) {
StringBuilder builder = new StringBuilder();
for (String rowWord : rectangle) {
builder.append(rowWord.charAt(col));
}
if (!prefixes.contains(builder.toString())) {
return false;
}
}
return true;
}
private boolean allColumnsAreWords(int rows, int cols) {
Set<String> wordSet = wordSetByLength.get(rows);
for (int col = 0; col < cols; col++) {
StringBuilder builder = new StringBuilder();
for (String rowWord : rectangle) {
builder.append(rowWord.charAt(col));
}
if (!wordSet.contains(builder.toString())) {
return false;
}
}
return true;
}
}
var wordsByLength map[int][]string
var wordSetByLength map[int]map[string]bool
var prefixSetByLength map[int]map[string]bool
var rectangle []string
func maxRectangle(words []string) []string {
buildWordData(words)
lengths := make([]int, 0, len(wordsByLength))
for length := range wordsByLength {
lengths = append(lengths, length)
}
sort.Sort(sort.Reverse(sort.IntSlice(lengths)))
answer := []string{}
bestArea := 0
maxLength := 0
if len(lengths) > 0 {
maxLength = lengths[0]
}
for _, cols := range lengths {
if cols*maxLength <= bestArea {
break
}
rowWords := wordsByLength[cols]
for _, rows := range lengths {
area := rows * cols
if area <= bestArea {
break
}
if wordSetByLength[rows] == nil {
continue
}
rectangle = []string{}
if backtrackRectangle(rowWords, rows, cols) {
bestArea = area
answer = append([]string{}, rectangle...)
break
}
}
}
return answer
}
func buildWordData(words []string) {
wordsByLength = map[int][]string{}
wordSetByLength = map[int]map[string]bool{}
prefixSetByLength = map[int]map[string]bool{}
for _, word := range words {
length := len(word)
wordsByLength[length] = append(wordsByLength[length], word)
if wordSetByLength[length] == nil {
wordSetByLength[length] = map[string]bool{}
}
if prefixSetByLength[length] == nil {
prefixSetByLength[length] = map[string]bool{}
}
wordSetByLength[length][word] = true
for end := 1; end <= length; end++ {
prefixSetByLength[length][word[:end]] = true
}
}
}
func backtrackRectangle(rowWords []string, rows int, cols int) bool {
if len(rectangle) == rows {
return allColumnsAreWords(rows, cols)
}
for _, word := range rowWords {
rectangle = append(rectangle, word)
if allColumnPrefixesExist(rows, cols) && backtrackRectangle(rowWords, rows, cols) {
return true
}
rectangle = rectangle[:len(rectangle)-1]
}
return false
}
func allColumnPrefixesExist(rows int, cols int) bool {
prefixes := prefixSetByLength[rows]
for col := 0; col < cols; col++ {
column := make([]byte, 0, len(rectangle))
for _, rowWord := range rectangle {
column = append(column, rowWord[col])
}
if !prefixes[string(column)] {
return false
}
}
return true
}
func allColumnsAreWords(rows int, cols int) bool {
wordSet := wordSetByLength[rows]
for col := 0; col < cols; col++ {
column := make([]byte, 0, len(rectangle))
for _, rowWord := range rectangle {
column = append(column, rowWord[col])
}
if !wordSet[string(column)] {
return false
}
}
return true
}
复杂度分析
- 设
W_c为长度 c 的可选行单词数。对固定r×c，最坏回溯树有O(W_c^r)个叶子；每个节点重建并检查列前缀最多O(rc)，所以上界为O(W_c^r·rc)。实际会被前缀集合大量剪枝。- 预处理若把每个单词的所有前缀物化，设字典总字符数为 D、最长词长为 L，时间与空间最坏为
O(DL)（哈希前缀需要读取前缀字符）。- 时间复杂度：
O(DL + Σ_(r,c) W_c^r·rc)，求和范围是所有未被面积上界剪掉的候选尺寸；该问题本身需要回溯搜索，不能笼统写成多项式。- 空间复杂度：
O(DL + r)，前缀/单词索引占主导，递归路径保存 r 行；不计返回结果。
关键点总结
- 行长决定列数、列长决定行数，两个维度不要写反。
- “每列是合法前缀”是从穷举降到可运行规模的核心剪枝。
- 面积上界剪枝只依赖剩余最大长度，不会漏掉更优尺寸。
- 面试追问可继续优化：回溯时增量维护 c 个列字符串，避免每层从头拼接；或为每个长度建立 Trie，用节点状态代替前缀字符串哈希。
易错点总结
- 错误写法：把行、列长度分组写反。以 3×4 矩形为反例，行应取长度 4、列应匹配长度 3；反过来会找不到示例答案。
- 只在放满 r 行后验证列：每层分支数都是
W_c，搜索接近完整的W_c^r；示例中若首行前缀就不存在，本可立即剪掉。- 前缀集合不按目标列长分组：某串可能是长度 5 单词的前缀，却无法补成长度 3 的列，错误保留死分支。
- 命中一个矩形立即结束全部搜索：当前枚举顺序不保证每个
(c,r)组合严格按面积全局降序，必须维护 bestArea 并继续检查仍可能更大的尺寸。- 回溯返回时忘记删除最后一行：下一分支会带着上一分支的残留行，列前缀与深度全部错位。
- 最终只检查前缀、不检查完整单词：若前缀集合实现不包含完整词，可能把未结束的列当成答案；显式完整集合检查更稳。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 425. 单词方块 | 困难 | 行列长度相等的前缀回溯 |
| 212. 单词搜索 II | 困难 | Trie 多词剪枝搜索 |
| 208. 实现 Trie | 中等 | 前缀索引基础 |