Given a set of wordswithout duplicates, find allword squaresyou 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
Notice
- There are at least 1 and at most 1000 words.
- All words will have the exact same length.
- Word length is at least 1 and at most 5.
- Each word contains only lowercase English alphabet
a-z.
Have you met this question in a real interview?
Yes
Example
Given a set ["area","lead","wall","lady","ball"]
return [["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).
Given a set ["abat","baba","atan","atal"]
return [["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:
/\*\*
\* @param words a set of words without duplicates
\* @return all word squares
\*/
vector<vector<string>> wordSquares\(vector<string>& words\) {
// Write your code here
if \(words.empty\(\)\) {
return squares;
}
initPrefix\(words\);
wordLen = words\[0\].size\(\);
search\(0\);
return squares;
}
bool checkPrefix\(int l, string nextWord\) {
for \(int j = l + 1; j < wordLen; ++j\) {
string pre;
for \(int i = 0; i < l; ++i\) {
pre += square\[i\]\[j\];
}
pre += nextWord\[j\];
if \(trieTree.FindByPrefix\(pre\).size\(\) == 0\) {
return false;
}
}
return true;
}
void search\(int l\) {
if \(l == wordLen\) {
squares.push\_back\(square\);
}
string pre = "";
for \(int i = 0; i < l; ++i\) {
pre += square\[i\]\[l\];
}
vector<string> nextWords = trieTree.FindByPrefix\(pre\);
for \(string& nextWord : nextWords\) {
if \(!checkPrefix\(l, nextWord\)\) {
continue;
}
square.push\_back\(nextWord\);
search\(l + 1\);
square.pop\_back\(\);
}
}
void initPrefix\(vector<string>& words\) {
for \(string& word : words\) {
trieTree.insert\(word\);
}
}
vector<vector<string>> squares;
vector<string> square;
int wordLen;
class TrieNode {
public:
TrieNode \(\) {
}
vector<string> startWith;
unordered\_map<char, TrieNode\*> children;
};
class Trie {
public:
Trie\(\){
root = new TrieNode\(\);
};
void insert\(string s\) {
TrieNode\* node = root;
for \(int i = 0; i < s.length\(\); ++i\) {
node->startWith.push\_back\(s\);
int ch = s\[i\] - 'a';
if \(!node->children.count\(ch\)\) {
node->children\[ch\] = new TrieNode\(\);
}
node = node->children\[ch\];
}
node->startWith.push\_back\(s\);
}
vector<string> FindByPrefix\(string prefix\) {
TrieNode\* node = root;
for \(int i = 0; i < prefix.length\(\); ++i\) {
int ch = prefix\[i\] - 'a';
if \(!node->children.count\(ch\)\)
return {};
node = node->children\[ch\];
}
return node->startWith;
}
TrieNode\* root;
};
Trie trieTree;
};