425 Word Squares

425. Word Squares

Given a set of words (without duplicates), find all word squares you can build from them.

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).

For example, the word sequence ["ball","area","lead","lady"] forms a word square because each word reads the same both horizontally and vertically.

b a l l
a r e a
l e a d
l a d y

Note:

1. There are at least 1 and at most 1000 words.
2. All words will have the exact same length.
3. Word length is at least 1 and at most 5.
4. Each word contains only lowercase English alphabet a-z.

Example 1:

Input:
["area","lead","wall","lady","ball"]

Output:
[
  [ "wall",
    "area",
    "lead",
    "lady"
  ],
  [ "ball",
    "area",
    "lead",
    "lady"
  ]
]

Explanation:
The output consists of two word squares. The order of output does not matter (just the order of words in each word square matters).

Example 2:

Input:
["abat","baba","atan","atal"]

Output:
[
  [ "baba",
    "abat",
    "baba",
    "atan"
  ],
  [ "baba",
    "abat",
    "baba",
    "atal"
  ]
]

Explanation:
The output consists of two word squares. The order of output does not matter (just the order of words in each word square matters).

分析&代码

这题其实没什么，就是要在比较grid[i][j]和grid[j][i]的时候一方面要注意横着的那个单词的长度有没有超过grid的行数，一方面也要注意竖过来之后，横着的长度够不够这个位置的。

public boolean validWordSquare(List<String> words) {
    if(words == null || words.size() == 0) {
        return false;
    }
    for(int i = 0; i < words.size(); i++) {
        int len = words.get(i).length();
        for(int j = 0; j < len; j++) {
            if(words.get(j).length() < i + 1 || words.get(i).length() > words.size() || words.get(j).charAt(i) != words.get(i).charAt(j)) {
                return false;
            }
        }
    }
    return true;
}