3799. Word Squares II
You are given a string array words, consisting of distinct 4-letter strings, each containing lowercase English letters.
A word square consists of 4 distinct words: top, left, right and bottom, arranged as follows:
top forms the top row.bottom forms the bottom row.left forms the left column (top to bottom).right forms the right column (top to bottom).
It must satisfy:
top[0] == left[0], top[3] == right[0]bottom[0] == left[3], bottom[3] == right[3]
Return all valid distinct word squares, sorted in ascending lexicographic order by the 4-tuple (top, left, right, bottom).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| class Solution {
public:
vector<vector<string>> wordSquares(vector<string>& words) {
sort(begin(words), end(words));
vector<vector<string>> res;
int n = words.size();
for(int top = 0; top < n; top++) {
for(int left = 0; left < n; left++) {
if(top == left) continue;
for(int right = 0; right < n; right++) {
if(top == right or left == right) continue;
for(int bottom = 0; bottom < n; bottom++) {
if(top == bottom or left == bottom or right == bottom) continue;
if(words[top][0] == words[left][0]) {
if(words[top][3] == words[right][0]) {
if(words[bottom][0] == words[left][3]) {
if(words[bottom][3] == words[right][3]) {
res.push_back({words[top],words[left],words[right],words[bottom]});
}
}
}
}
}
}
}
}
return res;
}
};
|
