单词方块

难度: Hard

Submission

运行时间: 168 ms

内存: 34.7 MB

from collections import defaultdict
class Solution:
    def wordSquares(self, words: List[str]) -> List[List[str]]:
        dct = defaultdict(list)
        for i in range(len(words)):
            for j in range(len(words[i])):
                dct[words[i][ : j]].append(i)
        # print(dct)

        # 回溯对象从 words（list) 转换成 dct
        def backtrack(path, res):
            if len(path) == len(words[0]):
                res.append(path[:])
                return
            # ball
            # area
            # lead
            # lady
            # e.g., k = 2
            # path = [ball, area]
            # 由此确定下一个词的前缀是 'le'
            k = len(path)
            prefix = ''
            for l in range(k):
                prefix += path[l][k]
            candidates = dct[prefix]
            for cand in candidates:
                path.append(words[cand])
                backtrack(path, res)
                path.pop()
        path = []
        res = []
        backtrack(path, res)
        return res

Explain

题解使用了回溯法结合哈希表预处理来解决单词方块问题。首先，创建一个字典，用于存储每个单词所有可能的前缀与对应单词的索引。这使得在构造方块时，可以迅速找到具有特定前缀的单词。接下来，使用回溯法生成所有可能的单词方块。回溯函数检查当前路径（已选的单词列表）的长度，如果达到单词的长度，则将其作为一个有效的解加入结果列表。否则，根据当前路径生成下一个单词的前缀，并查找字典中所有匹配这个前缀的单词。对于每一个找到的候选单词，将其加入到路径中，并递归继续尝试构造完整的方块，之后再将其从路径中移除。这样，所有可能的组合都会被尝试。

时间复杂度: O(n^m)

空间复杂度: O(n*m)

from collections import defaultdict
class Solution:
    def wordSquares(self, words: List[str]) -> List[List[str]]:
        dct = defaultdict(list)
        # 构建每个单词的前缀到单词索引的映射
        for i in range(len(words)):
            for j in range(len(words[i])):
                dct[words[i][ : j]].append(i)

        # 使用回溯法构建单词方块
        def backtrack(path, res):
            # 当前路径长度等于单词长度，记录结果
            if len(path) == len(words[0]):
                res.append(path[:])
                return
            # 生成下一个单词的前缀
            k = len(path)
            prefix = ''
            for l in range(k):
                prefix += path[l][k]
            # 寻找匹配的前缀
            candidates = dct[prefix]
            for cand in candidates:
                path.append(words[cand])
                backtrack(path, res)
                path.pop()
        path = []
        res = []
        backtrack(path, res)
        return res

Explore

在构建前缀字典时，包含空字符串作为前缀可以使得在回溯算法的起始阶段能够选择任何单词作为单词方块的开始。由于回溯的首次迭代需要选择第一个单词，而此时没有任何字符作为前缀，所以空字符串前缀允许我们从全部单词中选择开始构建单词方块的第一个单词。这种做法简化了算法的逻辑，确保了从每个可能的单词开始探索不同的单词方块组合。

在提供的题解代码中，确实没有明确的机制来阻止重复使用同一个单词。这可能导致在构建单词方块时重复使用某些单词。如果题目要求每个单词只能使用一次，那么应该在代码中加入一个标记数组或使用一个集合来跟踪哪些单词已被使用。每次从候选单词中选择一个单词时，将其标记为已使用，并在回溯回到上一层时取消标记。

在构建单词方块的过程中，每个单词都必须在其相应位置与其他单词的字符相匹配，形成有效的方块。使用已选单词的对角线字符来生成下一个单词的前缀是因为，单词方块是一个 N x N 的方阵，其中每行和每列都是有效的单词。因此，当选择下一个单词时，它的每个字符都必须与已选择单词的对应位置字符相匹配，这正是对角线字符所在的位置。这种方法确保了构建的是一个有效的单词方块，每一列也是一个合法的单词。

是的，如果在回溯过程中某个前缀没有找到任何匹配的单词，程序不会继续递归调用回溯函数，而是直接返回到上一层。这是因为没有候选单词可以继续构建单词方块，所以必须撤销上一步的选择（即从路径中移除最近添加的单词），然后尝试其他可能的单词选择。这种机制是回溯算法中的典型“试错”过程，即尝试每种可能的选择，如果当前选择不能成功解决问题，则取消当前选择并尝试下一种选择。