FXTi's blog
0%

valid-word-square

Posted on Edited on

Valid Word Square – LeetCode 422

Problem

Description

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.

Answer

Original

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    bool validWordSquare(vector<string>& words) {
        for (unsigned i = 0; i < words.size(); ++i) {
            for (unsigned 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;
    }
};

思路

由于是vector加string形成的二位数组，所以不方便直接获取列的长度信息，本质上就是一个循环比较问题。这个写法相当漂亮，因为分别对i和j两个下标变量进行交叉检查，于是间接达成了目的。时间复杂度$O(n)$，空间复杂度$O(1)$。

Better

思路

还没看到更好的思路。