原题链接在这里:
题目:
Given a sequence of words, check whether it forms a valid word square.
A sequence of words forms a valid word square if the th row and column read the exact same string, where 0 ≤ <max(numRows, numColumns).
Note:
.
- a-z
Example 1:
- Input:
- [
- "abcd",
- "bnrt",
- "crmy",
- "dtye"
- ]
- Output:
- true
- Explanation:
- The first row and first column both read "abcd".
- The second row and second column both read "bnrt".
- The third row and third column both read "crmy".
- The fourth row and fourth column both read "dtye".
- Therefore, it is a valid word square.
Example 2:
- Input:
- [
- "abcd",
- "bnrt",
- "crm",
- "dt"
- ]
- Output:
- true
- Explanation:
- The first row and first column both read "abcd".
- The second row and second column both read "bnrt".
- The third row and third column both read "crm".
- The fourth row and fourth column both read "dt".
- Therefore, it is a valid word square.
Example 3:
- Input:
- [
- "ball",
- "area",
- "read",
- "lady"
- ]
- Output:
- false
- Explanation:
- The third row reads "read" while the third column reads "lead".
- Therefore, it is NOT a valid word square.
题解:
检查是否关于对角线对称.
每一个 char 都要检查一遍. 这里注意内层 loop 不是从 i 开始而是从 0 开始. 原本想只检查右上部分在左下部分是否有对称即可,但忽略了这里不一定 size 是对称的,如果左下有这个 char 而右上没有这个 char 就不能检测出 false.
Time Complexity: O(m * n). m = words.size(). n 是最长 string 的 length.
Space: O(1).
AC Java:
- 1 public class Solution {
- 2 public boolean validWordSquare(List words) {
- 3
- if (words == null || words.size() == 0) {
- 4
- return true;
- 5
- }
- 6 int m = words.size();
- 7
- for (int i = 0; i) {
- 8
- for (int j = 0; j) {
- 9
- if (j >= m || i >= words.get(j).length() || words.get(i).charAt(j) != words.get(j).charAt(i)) {
- 10
- return false;
- 11
- }
- 12
- }
- 13
- }
- 14
- return true;
- 15
- }
- 16
- }
来源: