0425：单词方块（★★）

力扣第 425 题

题目

给定一个单词集合 words （没有重复），找出并返回其中所有的 单词方块 。 words 中的同一个单词可以被 多次 使用。你可以按 任意顺序 返回答案。

一个单词序列形成了一个有效的 单词方块 的意思是指从第 k 行和第 k 列 0 <= k < max(numRows, numColumns) 来看都是相同的字符串。

• 例如，单词序列 ["ball","area","lead","lady"] 形成了一个单词方块，因为每个单词从水平方向看和从竖直方向看都是相同的。

示例 1：

输入：words = ["area","lead","wall","lady","ball"]
输出: [["ball","area","lead","lady"],
["wall","area","lead","lady"]]
解释：
输出包含两个单词方块，输出的顺序不重要，只需要保证每个单词方块内的单词顺序正确即可。

示例 2：

输入：words = ["abat","baba","atan","atal"]
输出：[["baba","abat","baba","atal"],
["baba","abat","baba","atan"]]
解释：
输出包含两个单词方块，输出的顺序不重要，只需要保证每个单词方块内的单词顺序正确即可。

提示:

• 1 <= words.length <= 1000
• 1 <= words[i].length <= 4
• words[i] 长度相同
• words[i] 只由小写英文字母组成
• words[i] 都 各不相同

分析

假设某个有效的单词方块 A：

• 根据要求，第 i 个单词要满足 A[i][j]=A[j][i] ，对于 0<=j<=i-1
• 换句话说，根据前 i-1 个单词可以确定第 i 个单词的 i 位前缀
• 因此考虑提前将所有前缀存在哈希表中，即可加速回溯法的查找

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def wordSquares(self, words: List[str]) -> List[List[str]]:
        d = defaultdict(list)
        for w in words:
            for i in range(len(w)):
                d[w[:i]].append(w)
        res, path = [], []
        def dfs(i):
            if i==len(words[0]):
                res.append(path[:])
                return
            pre = ''.join(a[i] for a in path)
            for w in d[pre]:
                path.append(w)
                dfs(i+1)
                path.pop()
        dfs(0)
        return res

268 ms