LeetCode 面试题 17.25. 单词矩阵

2026-03-28 HGNULB 约 9 分钟

文章信息 3 个分类 4 个标签

分类

LeetCode 困难程序员面试金典（第 6 版）

题目描述

✅ 面试题 17.25. 单词矩阵

题意分析

用给定单词组成面积最大的字母矩形，每一行从左到右、每一列从上到下都必须是清单中的完整单词。同一个单词可以重复使用；行数与列数可以不同，存在多个最大面积答案时返回任意一个。

解法：按长度分组并用列前缀剪枝

核心思路

[!blue]

先固定矩形尺寸 rows × cols。每行有 cols 个字符，所以只能选择长度为 cols 的词；每列最终有 rows 个字符，所以列必须成为长度为 rows 的词。两种尺寸都来自清单中已有的单词长度，将单词按长度分组后，就能直接取得行候选。

对每一种完整词长度，另外保存该组单词的全部非空前缀，包含完整单词本身。逐行搭建矩形时，已经放入的字符不能再改变，因此每一列的当前字符串，都必须是某个目标长度为 rows 的词的前缀。只要一列不在对应前缀集合中，往下添加任何行都无法补救，立即放弃当前选择。

这个检查在未放满时只是必要条件，几列各自存在后续词，并不保证一定能找到共同的一行继续拼接，所以仍需回溯搜索。放满 rows 行后，每列前缀长度已经等于目标完整词长，此时属于该长度组的前缀集合就等价于属于完整词集合，无需再建立一份词表验证。

回溯每层尝试一个行词，先加入当前 rectangle，检查所有列前缀，再递归下一行。失败就移除刚加入的行，恢复上一层；成功则直接返回并保留完整路径。行词允许重复使用，因此每层都重新遍历全部行候选，不设置“该词已经使用”的标记。

尺寸按单词长度降序枚举。固定 cols 时，rows 也从大到小尝试：若面积已经不超过当前最优，后续更小高度都无法改进，可以结束这个宽度；第一次拼成合法矩形，也是该宽度能取得的最大高度。换一个宽度仍可能产生更大面积，所以不能直接结束全部搜索。

外层还可以用最大词长 maxLength 作上界。若当前 cols * maxLength 已经不超过最优面积，那么这个宽度与后续更小宽度都没有改善空间，可以整体停止。保存成功答案时复制行列表，后续新尺寸的回溯不会修改已记录的矩形。

解题步骤

按完整词长度建立行词列表，并为每个长度建立对应的前缀集合。

将不同长度降序排列，依次枚举行宽与目标行数，跳过无法增大面积的尺寸。

对固定尺寸逐行回溯，每加入一行就重新拼出各列当前前缀并查表。

前缀失败则撤销该行；达到目标高度就保留结果，更新最优面积。

继续检查仍可能改进的宽度，最后返回最大矩形的行列表。

代码实现

class Solution {
    private Map<Integer, List<String>> wordsByLength;
    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;
                }

                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<>();
        prefixSetByLength = new HashMap<>();

        for (String word : words) {
            int length = word.length();

            wordsByLength.computeIfAbsent(length, key -> new ArrayList<>()).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 true;
        }

        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;
    }
}

import (
    "sort"
)

var wordsByLength map[int][]string
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
            }

            rectangle = []string{}
            if backtrackRectangle(rowWords, rows, cols) {
                bestArea = area
                answer = append([]string{}, rectangle...)
                break
            }
        }
    }

    return answer
}

func buildWordData(words []string) {
    wordsByLength = map[int][]string{}
    prefixSetByLength = map[int]map[string]bool{}

    for _, word := range words {
        length := len(word)
        wordsByLength[length] = append(wordsByLength[length], word)
        if prefixSetByLength[length] == nil {
            prefixSetByLength[length] = map[string]bool{}
        }

        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 true
    }

    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
}

复杂度分析

时间复杂度：设 N 为单词数、D 为总字符数、L 为最长词长，前缀构造与哈希预处理上界为 $O(N+DL)$。固定 r × c、长度为 c 的行词数为 W_c 时，搜索树深度为 r，每个尝试需重建至多 c 个长度不超过 r 的列前缀，通用上界为 $O(W_c^r r^2c)$；再对实际检查的尺寸求和。前缀剪枝减少实际分支，最坏复杂度仍为指数级。

空间复杂度：统一上界为 $O(N+DL+L)$。Java 会复制前缀字符串，Go 前缀切片可共享原字符串内容；另外保存分组、至多 L 行的当前矩形和递归栈。

关键点总结

[!green]

行宽决定行词长度，行数决定列词长度，两个分组不能混用。

前缀失败可以立即剪枝，前缀长度达到目标高度时就已经是完整词。

固定宽度下高度递减，结合当前最优面积与最大词长才能安全提前停止。

易错点总结

[!yellow]

只在放满后检查列，会让大量早已不可能成功的前缀继续展开。

列前缀必须查目标列长对应的集合，不能在其他长度单词的前缀中找到就接受。

给行词加已使用标记，会错误禁止题目允许的重复用词。

失败时要撤销最后一行，成功时要保留路径；不同宽度之间也要重新开始候选矩形。

只找到第一个合法尺寸就结束全部搜索，可能遗漏更大面积的其他宽度。

相似题目

题目	难度	关联与区别
425. 单词方块	困难	同样逐行构造并剪枝列前缀，原题限定正方形，本题允许行数与列数不同并最大化面积。
208. 实现 Trie (前缀树)	中等	前缀集合可替换为Trie，逐层保存每列节点以避免反复拼接前缀。

.article-image.is-loading { width: var(--article-image-width, 100%); height: auto; } .article-image.is-loading img { position: static; width: auto !important; height: auto !important; opacity: 1; pointer-events: auto; } .article-image-spinner { display: none; }

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2026/56760955

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！