888. 有效单词词广场

2018-07-03

Description

给定一个单词序列，检查它是否构成一个有效单词广场。
一个有效的单词广场满足：如果第k行和第k列读取相同的字符串,并且0≤k<max(numRows numColumns)。

Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
给定
[
  "abcd",
  "bnrt",
  "crmy",
  "dtye"
]
返回 true

解释:
第一行和第一列都是“abcd”。
第二行和第二列都是“bnrt”。
第三行和第三列都是“crmy”。
第四行和第四列都是“dtye”。

因此，这是一个有效的单词广场.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
给定
[
  "abcd",
  "bnrt",
  "crm",
  "dt"
]
返回 true

解释:
第一行和第一列都是“abcd”。
第二行和第二列都是“bnrt”。
第三行和第三列都是“crm”。
第四行和第四列都是“dt”。

因此，这是一个有效的单词广场.
1
2
3
4
5
6
7
8
9
10
11
12
13
给定
[
  "ball",
  "area",
  "read",
  "lady"
]
返回 false

解释:
第三行是 "read" 但是第三列是 "lead".

因此，这不是一个有效的单词广场.

Solution 1

直接暴力两层for, skip, O(n^m)

SOlution 2

发现跟前面做过的Toeplitz Matrix有点像，直接忽略对角线判断Matrix[i][j] == Matrix[j][i]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * @param words: a list of string
 * @return: a boolean
 */
const validWordSquare = function (words) {
    let colwords = [];
    let cols = words[0].length;
    let row = words.length;
    let offset = 0;
    for (let i = 1;i<cols;i++){
        if (offset == row-1)break;
        if (words[i-1 + offset][i + offset] !== words[i + offset][i-1 + offset])
            return false;
        if (i == cols){
            i = 1;
            offset++;
        }
    }
    return true;
}