LeetCode 第422题：有效的单词方阵

📖 文章摘要

本文详细解析LeetCode第422题“有效的单词方阵”，这是一道字符串处理的题目。文章提供了基于矩阵对称性检查的解题思路，包含C#、Python、C++三种语言实现，配有详细的图解分析和性能分析。适合对字符串处理和矩阵操作感兴趣的读者。

核心知识点： 字符串处理、矩阵操作、对称性判断
难度等级： 简单
推荐人群： 具有基础编程能力，对字符串和矩阵处理感兴趣的程序员

题目描述

给你一个单词序列，判断其是否形成了一个有效的单词方阵。

有效的单词方阵是指：从第 k 行和第 k 列读出的字符串应当相同，其中 0 ≤ k < max(numRows, numColumns)。

注意：

给定的单词数量至少为 1，且不超过 500。
每个单词的长度至少为 1，且不超过 500。
每个单词只包含小写英文字母 a-z。

示例

示例 1：

输入：
[
  "abcd",
  "bnrt",
  "crmy",
  "dtye"
]
输出：true
解释：
第1行和第1列都是 "abcd"
第2行和第2列都是 "bnrt"
第3行和第3列都是 "crmy"
第4行和第4列都是 "dtye"

示例 2：

输入：
[
  "abcd",
  "bnrt",
  "crm",
  "dt"
]
输出：true
解释：
第1行和第1列都是 "abcd"
第2行和第2列都是 "bnrt"
第3行和第3列都是 "crm"
第4行和第4列都是 "dt"

示例 3：

输入：
[
  "ball",
  "area",
  "read",
  "lady"
]
输出：false
解释：
第3行读作 "read" 而第3列读作 "lead"

解题思路

解法一：直接比较法

基本思路：
- 遍历每个位置 (i, j)，检查 words[i][j] 是否等于 words[j][i]
- 需要注意处理字符串长度不一致的情况
- 如果任何位置的字符不相等，则返回false
具体步骤：
- 遍历每个单词
- 对于每个单词的每个字符位置，检查对应的转置位置
- 处理越界情况
- 比较对应位置的字符

解法二：预处理法

基本思路：
- 先将所有单词补齐为相同长度
- 然后直接比较对应位置的字符
具体步骤：
- 找到最长单词的长度
- 将所有单词补齐到相同长度
- 逐个比较对应位置的字符

图解思路

矩阵对称性分析表

位置	原始字符	转置字符	是否相等	说明
(0,0)	a	a	是	对角线位置
(0,1)	b	b	是	对称位置
(0,2)	c	c	是	对称位置
(1,1)	n	n	是	对角线位置
…	…	…	…	…

边界情况分析表

情况	处理方法	示例
字符串长度不等	较短的视为有效	“abc” vs “a”
越界访问	返回false	访问不存在的位置
空字符串	特殊处理	“”

代码实现

C# 实现

public class Solution {
    public bool ValidWordSquare(IList<string> words) {
        if (words == null || words.Count == 0) return true;
        
        for (int i = 0; i < words.Count; i++) {
            for (int j = 0; j < words[i].Length; j++) {
                if (j >= words.Count || 
                    i >= words[j].Length || 
                    words[i][j] != words[j][i]) {
                    return false;
                }
            }
        }
        return true;
    }
}

Python 实现

class Solution:
    def validWordSquare(self, words: List[str]) -> bool:
        if not words:
            return True
            
        for i in range(len(words)):
            for j in range(len(words[i])):
                if j >= len(words) or i >= len(words[j]) or words[i][j] != words[j][i]:
                    return False
        return True

C++ 实现

class Solution {
public:
    bool validWordSquare(vector<string>& words) {
        if (words.empty()) return true;
        
        for (int i = 0; i < words.size(); i++) {
            for (int j = 0; j < words[i].size(); j++) {
                if (j >= words.size() || 
                    i >= words[j].size() || 
                    words[i][j] != words[j][i]) {
                    return false;
                }
            }
        }
        return true;
    }
};

执行结果

C# 实现

执行用时：96 ms
内存消耗：40.2 MB

Python 实现

执行用时：36 ms
内存消耗：15.1 MB

C++ 实现

执行用时：8 ms
内存消耗：8.4 MB

性能对比

语言	执行用时	内存消耗	特点
C#	96 ms	40.2 MB	实现简单，性能中等
Python	36 ms	15.1 MB	代码简洁，内存占用小
C++	8 ms	8.4 MB	执行效率最高

代码亮点

🎯 简洁的边界条件处理
💡 高效的矩阵遍历方式
🔍 优雅的对称性检查
🎨 清晰的代码结构

常见错误分析

🚫 忽略了字符串长度不一致的情况
🚫 没有处理数组为空的边界情况
🚫 越界访问导致运行时错误
🚫 对称位置判断逻辑错误

解法对比

解法	时间复杂度	空间复杂度	优点	缺点
直接比较法	O(n*m)	O(1)	实现简单，空间效率高	需要处理边界情况
预处理法	O(n*m)	O(n*m)	逻辑清晰	额外空间开销大

📖 系列导航

🔥 字符串专题合集 - 查看完整合集

📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新第422题。

💬 互动交流

感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。

如果这篇文章对你有帮助，请：

👍 点个赞，让更多人看到这篇文章
📁 收藏文章，方便后续查阅复习
🔔 关注作者，获取更多高质量算法题解
💭 评论区留言，分享你的解题思路或提出疑问

你的支持是我持续分享的动力！

💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！

📖 文章摘要

题目描述

示例

示例 1：

示例 2：

示例 3：

解题思路

解法一：直接比较法

解法二：预处理法

图解思路

矩阵对称性分析表

边界情况分析表

代码实现

C# 实现

Python 实现

C++ 实现

执行结果

C# 实现

Python 实现

C++ 实现

性能对比

代码亮点

常见错误分析

解法对比

相关题目

📖 系列导航

💬 互动交流