ValidWordSquareOPT [source code]

public class ValidWordSquareOPT {
static
/******************************************************************************/
public class Solution {
    public boolean validWordSquare(List<String> words) {
        if (words == null || words.size() == 0) {
            return false;
        }
        int n = words.size();
        char[][] arr = new char[n][n];

        for (int i = 0; i < n; i++) {
            char[] t = words.get(i).toCharArray();
            if (t.length > n) {
                return false;
            }

            for (int j = 0; j < t.length; j++) {
                arr[i][j] = t[j];
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if (arr[i][j] != arr[j][i]) {
                    return false;
                }
            }
        }

        return true;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        ValidWordSquareOPT.Solution tester = new ValidWordSquareOPT.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));
    }
}

这个是 submission 最优解, 速度跟我的 ver1其实是一样的, 不过算法更聪明; 自己在纸上画一下就知道, 他这个算法, 没有任何的重复比较, 也就是有一个类似 stream 算法里面可以复用前面的 i 的比较结果的作用(前面的 i 比较过的地方, 后面的 i 就不用比较了);

大概算一下的话, 这个做法可以把复杂度砍一半. 虽然没有数量级上的改变, 不过还是不小的加速;

另外他这类初始化的时候就检查了一下词长不能超过list length, 这个我没想到;

我感觉我这个问题没有想到更好的算法的一个原因是过分追求 general, 也就是故意想让我的算法可以应对任何词长的情况, 但是这个就增加了后面算法设计的难度; 他们的这几个算法, 基本都是直接上来先规范这个矩阵的维度. 这个规范的好处在于:

1. 首先, 如果确实维度就不合法, 就可以提前直接先淘汰, 这个其实在大量 Test Case 的情况下, 是可以达到加速的目的的;
2. 写后面的代码的时候, 我们无形中就有了一个 implicit 的 assumption, 类似loop termination condition, 这样有这么一个(关于维度的)隐藏条件之后, 后面写比较算法的时候就难度也降低很多;

算法设计, 以前也说过了, 基本还是要有一个example-oritented的精神, 不停的举出不同的例子, 然后想想怎样让你的代码可以 handle 这些例子; 尤其是这个题目, 二维数组, 你不画例子看, 托着脑袋想是很慢的;

discussion 上面还看到一个更加奇葩的比较方法, 可以跳过对角线, 不过这种就没多大差别了, 而且代码看起来也难读很多;

看了一下 discussion 上面, 其他的代码基本就是鸡毛蒜皮的改动了, 这个题目到此为止;

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