# 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  k th 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:

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

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

``````class Solution {
public:
vector<vector<string>> wordSquares(vector<string>& words) {
vector<vector<string>> res;
unordered_map<string, set<string>> m;
int n = words[0].size();
for (string word : words) {
for (int i = 0; i < n; ++i) {
string key = word.substr(0, i);
m[key].insert(word);
}
}
vector<vector<char>> mat(n, vector<char>(n));
helper(0, n, mat, m, res);
return res;
}
void helper(int i, int n, vector<vector<char>>& mat, unordered_map<string, set<string>>& m, vector<vector<string>>& res) {
if (i == n) {
vector<string> out;
for (int j = 0; j < n; ++j) out.push_back(string(mat[j].begin(), mat[j].end()));
res.push_back(out);
return;
}
string key = string(mat[i].begin(), mat[i].begin() + i);
for (string str : m[key]) {
mat[i][i] = str[i];
int j = i + 1;
for (; j < n; ++j) {
mat[i][j] = str[j];
mat[j][i] = str[j];
if (!m.count(string(mat[j].begin(), mat[j].begin() + i + 1))) break;
}
if (j == n) helper(i + 1, n, mat, m, res);
}
}
};
``````

``````class Solution {
public:
struct TrieNode {
vector<int> indexs;
vector<TrieNode*> children;
TrieNode(): children(26, nullptr) {}
};
TrieNode* buildTrie(vector<string>& words) {
TrieNode *root = new TrieNode();
for (int i = 0; i < words.size(); ++i) {
TrieNode *t = root;
for (int j = 0; j < words[i].size(); ++j) {
if (!t->children[words[i][j] - 'a']) {
t->children[words[i][j] - 'a'] = new TrieNode();
}
t = t->children[words[i][j] - 'a'];
t->indexs.push_back(i);
}
}
return root;
}
vector<vector<string>> wordSquares(vector<string>& words) {
TrieNode *root = buildTrie(words);
vector<string> out(words[0].size());
vector<vector<string>> res;
for (string word : words) {
out[0] = word;
helper(words, 1, root, out, res);
}
return res;
}
void helper(vector<string>& words, int level, TrieNode* root, vector<string>& out, vector<vector<string>>& res) {
if (level >= words[0].size()) {
res.push_back(out);
return;
}
string str = "";
for (int i = 0; i < level; ++i) {
str += out[i][level];
}
TrieNode *t = root;
for (int i = 0; i < str.size(); ++i) {
if (!t->children[str[i] - 'a']) return;
t = t->children[str[i] - 'a'];
}
for (int idx : t->indexs) {
out[level] = words[idx];
helper(words, level + 1, root, out, res);
}
}
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/425

Valid Word Square

https://leetcode.com/problems/word-squares/

https://leetcode.com/problems/word-squares/discuss/91380/java-53ms-dfs-hashmap

https://leetcode.com/problems/word-squares/discuss/91344/Short-PythonC%2B%2B-solution

https://leetcode.com/problems/word-squares/discuss/91333/Explained.-My-Java-solution-using-Trie-126ms-1616

https://leetcode.com/problems/word-squares/discuss/91337/70ms-Concise-C%2B%2B-Solution-Using-Trie-and-Backtracking

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation