当前位置：首页>Word>单词方块 Word Square

单词方块 Word Square

2026-04-07 10:38:41

先吃饭吧。

Given an array of unique strings words, return all the word squares you can build from words. The same word from wordscan be used multiple times. You can return the answer in any order.

A sequence of strings forms a valid word square if the kth row and column read the same string, where 0 <= k < max(numRows, numColumns).

For example, the word sequence ["ball","area","lead","lady"] forms a word square because each word reads the same both horizontally and vertically.

Example 1:

Input: words = ["area","lead","wall","lady","ball"]Output: [["ball","area","lead","lady"],["wall","area","lead","lady"]]Explanation:The output consists of two word squares. The order of output does not matter (just the order of words in each word square matters).

重要约束：

所有单词长度一致，区分大小写，无重复单词。
要求第k行和第k列相同（严格结构对称）
每个位置可以自由选择单词，但是这些选择相互制约

矛盾的展开：

选择第一行单词，也决定了第一列的前缀
选择第二行单词时，必须同时满足第一列的前缀（r=0, c=0) ，和第二列的前缀（(r=0, c=1) (r=1, c=0)）
每一行选择都影响所有列的前缀构建

次要矛盾：

全局约束vs局部选择：每个单词看似局部，但影响全局所有列
指数搜索空间vs多项式时间：理论上指数级排列，需要高效剪枝
前缀匹配精确性vs回溯灵活性

矛盾的下放：

整体Word Square构建问题

↓ 分解为

逐行构建问题

↓ 分解为

每行选择时对每列前缀的匹配问题

↓ 分解为

每个前缀在字典中的存在性检查问题

矛盾的转化机制：

从结构约束到前缀约束：将网格对称性转化为每列前缀匹配要求
从全局检查到局部递推：每行只需保证当前所有列前缀有效，后续行继续验证
从穷举搜索到剪枝优化：通过前缀匹配提前排除无效分支

工具选择：Trie+Backtracking的必然性

为什么Backtracking是必要的？

问题本质是组合搜索：需要尝试所有可能的单词排列
选择具有后效性：当前选择影响后续选择空间
需要探索和回溯：错误选择需要撤销，尝试其他可能性

为什么Trie是关键的优化武器？

快速前缀检查：Word Square构建过程中核心操作是"给定前缀，有哪些单词匹配"
空间换时间：预构建Trie避免每次线性搜索字典
支持增量更新：随着网格构建，前缀逐渐变长，Trie支持高效扩展

矛盾的初始解决尝试：朴素Backtracking

def backtrack(step, grid, words):    if step == n:  # 完成所有行        if check_columns(grid):  # 检查所有列是否也是单词            add_solution(grid)        return    for word in words:        if valid_prefixes(step, grid, word):  # 检查当前选择是否保持所有前缀有效            grid[step] = word            backtrack(step+1, grid, words)            grid[step] = None  # 回溯

问题：每次检查所有列前缀需要O(n)时间，且需要线性搜索匹配单词

矛盾未充分转化：检查效率低下

矛盾的有效转化：Trie优化的Backtracking

from collections import defaultdictfrom typing import Listclass TrieNode:    def __init__(self):        self.children = defaultdict(TrieNode)        self.word_indices = []  # 存储以当前节点为前缀的单词索引class WordSquareSolver:    def __init__(self, words: List[str]):        self.words = words        self.n = len(words[0])  # 单词长度，也是网格大小        self.trie = self._build_trie()        self.result = []    def _build_trie(self):        """构建前缀树，每个节点存储以该节点为前缀的单词索引"""        root = TrieNode()        for idx, word in enumerate(self.words):            node = root            node.word_indices.append(idx)  # 空字符串是所有单词的前缀            for ch in word:                node = node.children[ch]                node.word_indices.append(idx)        return root    def _get_words_with_prefix(self, prefix: str) -> List[int]:        """获取具有指定前缀的所有单词索引"""        node = self.trie        for ch in prefix:            if ch not in node.children:                return []            node = node.children[ch]        return node.word_indices    def _has_prefix(self, prefix: str) -> bool:        """检查前缀是否存在"""        node = self.trie        for ch in prefix:            if ch not in node.children:                return False            node = node.children[ch]        return True    def find_word_squares(self) -> List[List[str]]:        """查找所有 word squares"""        if not self.words or not self.words[0]:            return []        # 初始化：每列的前缀都是空字符串        col_prefixes = ["" for _ in range(self.n)]        used = [False] * len(self.words)  # 标记单词是否使用过        current_rows = []  # 当前已放置的行        def backtrack(step: int):            """递归回溯            step: 当前要放置的行索引（0-based）            """            if step == self.n:                # 检查所有列是否都是有效单词                if all(self._has_prefix(col_prefixes[j]) and                        any(self.words[idx] == col_prefixes[j]                            for idx in self._get_words_with_prefix(col_prefixes[j]))                        for j in range(self.n)):                    self.result.append(current_rows[:])                return            # 获取第step列当前前缀的所有可能单词            col_prefix = col_prefixes[step]            candidate_indices = self._get_words_with_prefix(col_prefix)            for idx in candidate_indices:                if used[idx]:                    continue                word = self.words[idx]                # 计算新的列前缀                new_prefixes = col_prefixes[:]  # 创建副本                for j in range(self.n):                    new_prefixes[j] = new_prefixes[j] + word[j]                # 检查所有新前缀是否有效（即是否存在以该前缀开头的单词）                if all(self._has_prefix(new_prefixes[j]) for j in range(step + 1, self.n)):                    used[idx] = True                    current_rows.append(word)                    # 保存旧前缀，递归后恢复                    old_prefixes = col_prefixes[:]                    col_prefixes[:] = new_prefixes                    backtrack(step + 1)                    # 回溯                    col_prefixes[:] = old_prefixes                    current_rows.pop()                    used[idx] = False        backtrack(0)        return self.resultclass Solution:    def wordSquares(self, words: List[str]) -> List[List[str]]:        """主函数"""        if not words:            return []        solver = WordSquareSolver(words)        return solver.find_word_squares()# 测试代码if __name__ == "__main__":    # 示例测试    words1 = ["area","lead","wall","lady","ball"]    words2 = ["abat","baba","atan","atal"]    sol = Solution()    print("测试1:")    result1 = sol.wordSquares(words1)    for square in result1:        print(square)    print("\n测试2:")    result2 = sol.wordSquares(words2)    for square in result2:        print(square)    # 性能测试：n=4，单词较多的情况    words3 = [        "rose", "oven", "send", "ends",        "nose", "ones", "done", "node",        "dose", "dots", "stop", "tops"    ]    print("\n测试3:")    result3 = sol.wordSquares(words3)    print(f"找到 {len(result3)} 个 word squares")    for square in result3[:3]:  # 只显示前3个        print(square)