有效的单词方块

Submission

运行时间: 28 ms

内存: 17.0 MB

class Solution:
    def validWordSquare(self, words: List[str]) -> bool:
        return all(
            x == "".join(y)
            for x, y in zip(
                words,
                zip_longest(*words, fillvalue="")
            )
        )

Explain

这个题解利用了 Python 的一些特性来简洁地解决问题。首先使用 zip 函数将 words 数组和它的转置（通过 zip(*words) 实现）配对。由于不同单词长度可能不同，使用 zip_longest 并填充空字符串来处理长度不一致的情况。最后用 all 函数检查每个单词是否与其对应的转置相等。

时间复杂度: O(nm)

空间复杂度: O(nm)

class Solution:
    def validWordSquare(self, words: List[str]) -> bool:
        return all(
            x == "".join(y)  # 比较每个单词 x 与其转置 y 是否相等
            for x, y in zip(  # 将 words 与其转置 zip 后逐对比较
                words,
                zip_longest(*words, fillvalue="")  # 转置 words，不等长时填充空串  
            )
        )

Explore

在这个问题的场景中，`zip_longest`用来确保可以遍历到所有单词的最大长度，即使某些单词长度不足。使用空字符串作为填充值是因为它是字符串操作中的中性元素，不会改变其他字符串的内容。在比较单词与其垂直读取的串时，若不使用空字符串填充较短的单词，那么较短单词的长度将无法匹配较长单词的长度，导致比较结果错误。因此，使用空字符串填充可以保证每一列的长度一致，从而准确比较单词与其垂直对应的字符串是否相同。

当处理含有不同长度单词的列表时，使用`zip_longest`函数填充空字符串保证了所有单词在转置时能形成等长的列。这种方式允许算法有效处理不同长度的单词，因为比较时较短的单词通过空字符串填充到与最长的单词相同的长度。如果某些单词长度短于其他单词，转置后的结果将用空字符串补足缺失的部分，使得每个单词的长度都等于最长单词的长度，从而确保比较的公平性和正确性。

当单词数组`words`为空时，`zip_longest`不会生成任何元素，因此`all`函数会直接返回`True`，这在逻辑上是合理的，因为空列表理论上是一个有效的单词方块。如果列表只包含一个元素，该元素将与其自身进行比较，由于单词与其自身总是相等的，因此这也会返回`True`。因此，这个算法在这些特殊情况下能正确运行，无需特别处理。

Python的字符串处理对于非ASCII字符如中文是友好的，因为Python字符串是基于Unicode的。这意味着，无论是ASCII字符还是非ASCII字符（如中文），`zip_longest`和字符串的比较操作都是按照Unicode字符进行处理的。因此，该算法处理包含非ASCII字符的输入在逻辑上与处理ASCII字符相同，不需要任何特别的修改或考虑。