422. Valid Word Square

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 k^th row and column read the exact same string, where 0 ≤ k < max(numRows, numColumns).

Note:

1. The number of words given is at least 1 and does not exceed 500.
2. Word length will be at least 1 and does not exceed 500.
3. 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.

Solution

Iteration, O(n ^ 2), S(n)

这道题还蛮有意思的，其实就是比较从(i, i)开始，该行和该列对应的string是否equal。corner case还是很多的，例如s1和s2长度不等，或者里面的字符不一样，还有words可以是长度参差不齐的。处理起来还挺复杂。

我想出一个办法是，由于题目中保证只有lowercase letter，我们先找到(i, i)对应的row string s1，然后再竖着遍历，找到对应的col string s2，比较tricky的地方是，如果遍历到某行长度小于i，则append一个" "。这样最后对s2取trim，就能干掉结尾连续的" "。这样长度层次不齐的情况就能被handle了。

class Solution {
    public boolean validWordSquare(List<String> words) {
        if (words == null) {
            return false;
        }
        
        int m = words.size();
        
        for (int i = 0; i < m; ++i) {
            String s1 = i < words.get(i).length() 
                ? words.get(i).substring(i) : "";
            StringBuilder sb = new StringBuilder();
            
            for (int j = i; j < m; ++j) {
                String word = words.get(j);
                sb.append(i < word.length() ? word.charAt(i) : " ");    
            }
            
            if (!s1.equals(sb.toString().trim())) { // tricky
                return false;
            }
        }
        
        return true;
    }
}