ValidWordSquare [source code]

public class ValidWordSquare {
static
/******************************************************************************/
public class Solution {
    public boolean validWordSquare(List<String> words) {
        int m = words.size();
        if (m == 0) return false;
        String[] ar = words.toArray(new String[0]);
        char[][] letters = new char[m][];
        for (int i = 0; i < m; i++) {
            letters[i] = ar[i].toCharArray();
        }
        for (int i = 0; i < m; i++) {
            int n = letters[i].length;
            for (int j = 0; j < n; j++) {
                if (j >= m || i >= letters[j].length || letters[i][j] != letters[j][i]) return false;
            }
            if (n < m) {
                for (int j = n; j < m; j++) {
                    if (letters[j].length >= i + 1) return false;
                }
            }
        }
        return true;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        ValidWordSquare.Solution tester = new ValidWordSquare.Solution();
        List<List<String>> inputs = new ArrayList<>();
        inputs.add(Arrays.asList(new String[]{
            "abcd",
            "bnrt",
            "crmy",
            "dtye"
        }));
        inputs.add(Arrays.asList(new String[] {
            "abcd",
            "bnrt",
            "crm",
            "dt"
        }));
        inputs.add(Arrays.asList(new String[] {
            "ball",
            "area",
            "read",
            "lady"            
        }));
        inputs.add(Arrays.asList(new String[]{"ball","asee","lett","le"}));
        int counter = 0;
        for (List<String> ls : inputs) System.out.println((++counter) + " -> " + tester.validWordSquare(ls));
    }
}

这个题目总体的思路是有的, 不过这个 Google 的题目, 你应该猜到了, 重点其实还是在 Corner Case 和各种细节参数的设置上面, 这个也是为什么 Google 的面试都要求一遍过;

这个题目的难点在于如果 word 的长度不齐的情况怎么处理; 我这里的处理方法是第一个循环比对字母对应, 然后第二个循环专门来检查一下没有被比对到的 word 位置的 word 长度不能超过 i, 意思是不能继续有 word 了;
这个方法其实是比较麻烦的, 因为你第一个循环的时候要加边界检查, 然后第二个循环这个 word 长度的 limit 值究竟是多少? 这个实际自己写的时候其实还是挺容易写错的, 我刚开始 i 和 n 都试过了, 都不对;

另外注意一些语法上的小细节:

java> int[][] table = new int[3][]  
int[][] table = [null, null, null]  
java> table[1] = {1,2}  
ERROR: ...  
java> table[1] = new int[]{1,2}  
int[] res1 = [1, 2]

可以看到, 这里在给二维数组的第二维 assign 的时候, 直接甩一个 literal 是不行的, 必须给一个 object 才行;

最后的速度是9ms (98%), 算是最优解了, 还是有点没有想到的, 可能跟我一开始直接转换成为二维数组有点关系;

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.
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.
Seen this question in a real interview before? Yes No
Difficulty:Easy
Total Accepted:10K
Total Submissions:27.6K
Contributor: LeetCode
Companies
google
Similar Questions
Word Squares