LeetCode刷题实战422：有效的单词方块

清疚 2022-09-17 05:15 162阅读 0赞

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选 ！

今天和大家聊的问题叫做 **有效的单词方块**，我们先来看题面：

https://leetcode-cn.com/problems/valid-word-square/

Given a sequence of words, check whether it forms a valid word square.

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

Note:

The number of words given is at least 1 and does not exceed 500.

Word length will be at least 1 and does not exceed 500.

Each word contains only lowercase English alphabet a-z.

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

有效的单词方块是指此由单词序列组成的文字方块的 第 k 行 和 第 k 列 (0 ≤ k < max(行数, 列数)) 所显示的字符串完全相同。

注意：

给定的单词数大于等于 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"。
    因此，这 不是 一个有效的单词方块。

## **解题** ##

检查单词长度是否等于单词个数，有长的，直接返回false，如果比较短的，补上空格 。

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

好了，今天的文章就到这里，如果觉得有所收获，请顺手点个**在看**或者转发吧，你们的支持是我最大的动力 。

**上期推文：**

[LeetCode1-420题汇总，希望对你有点帮助！][LeetCode1-420]

[LeetCode刷题实战421：数组中两个数的最大异或值][LeetCode_421]

![b9cc6f43a449d04ac3ceab222d6725cf.png][]

[LeetCode1-420]: https://blog.csdn.net/itcodexy/article/details/109832160
[LeetCode_421]: https://blog.csdn.net/itcodexy/article/details/111772001
[b9cc6f43a449d04ac3ceab222d6725cf.png]: /images/20220828/76894a3afafe468c92d6b6d493f96ab5.png