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:
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.
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).
S1： Trie， backtracking （time complexity?）
从square第二行开始，每一行的前缀由它前面行决定，s[i][j] = s[j][i]. 确定第一行之后，用backtracking尝试满足前缀要求的所有word。简历trie为了方便找到拥有某一前缀的所有words
struct TrieNode{
char c;
vector<TrieNode*> children;
TrieNode(char x) : c(x), children(26, nullptr) {};
};
class Solution {
public:
vector<vector<string>> wordSquares(vector<string>& words) {
vector<vector<string>> result;
if (words.size() == 0) return result;
root = new TrieNode('@');
for (string& s : words) addWord(root, s, 0);
size = words[0].size();
for (string& s : words) {
vector<string> square(size, s);
getSquares(words, 1, square, result);
}
return result;
}
void getSquares(vector<string>& words, int i, vector<string> square, vector<vector<string>>& result) {
if (i == size) {
result.push_back(square);
return;
}
string prefix = "";
for (int k = 1; k <= i; ++k) {
prefix += square[prefix.size()][i];
}
vector<string> strs;
getPrefix(root, prefix, 0, "", strs);
if (strs.size() > 0) {
for (string& s : strs) {
square[i] = s;
getSquares(words, i + 1, square, result);
}
}
}
private:
TrieNode *root;
int size;
void addWord(TrieNode* root, string& str, int i) {
if (i == str.size()) return;
if (root->children[str[i] - 'a'] == nullptr) {
root->children[str[i] - 'a'] = new TrieNode(str[i]);
}
addWord(root->children[str[i] - 'a'], str, i + 1);
}
void getPrefix(TrieNode* node, string prefix, int i, string s, vector<string>& strs) {
if (s.size() == size) {
strs.push_back(s);
return;
}
if (i < prefix.size()) {
if (node->children[prefix[i]-'a'] == nullptr) return;
s += prefix[i];
getPrefix(node->children[prefix[i]-'a'], prefix, i + 1, s, strs);
} else {
bool result = false;
for (TrieNode* child : node->children) {
if (child != nullptr)
getPrefix(child, prefix, i + 1, s + child->c, strs);
}
}
}
};
S2：backtracking
因为这里word长度不超过5，可以直接存储prefix对应word，直接O(1)查询
class Solution {
public:
vector<vector<string>> wordSquares(vector<string>& words) {
vector<vector<string>> result;
if (words.size() == 0) return result;
size = words[0].size();
wordList = words;
for (int i = 0; i < words.size(); ++i) {
addWord(words[i], 1, i);
}
for (string& s : words) {
vector<string> square(size, s);
getSquares(1, square, result);
}
return result;
}
void getSquares(int i, vector<string> square, vector<vector<string>>& result) {
if (i == size) {
result.push_back(square);
return;
}
string prefix = "";
for (int k = 1; k <= i; ++k) {
prefix += square[prefix.size()][i];
}
if (prefixMap.find(prefix) != prefixMap.end()) {
for (int idx : prefixMap[prefix]) {
square[i] = wordList[idx];
getSquares(i + 1, square, result);
}
}
}
private:
int size;
vector<string> wordList;
unordered_map<string, vector<int>> prefixMap;
void addWord(string& str, int i, int idx) {
if (i == str.size()) return;
string prefix = str.substr(0, i);
if (prefixMap.find(prefix) == prefixMap.end()) {
prefixMap[prefix] = vector<int>{idx};
} else {
prefixMap[prefix].push_back(idx);
}
addWord(str, i + 1, idx);
}
};
422. Valid Word Square
Given a sequence of words, check whether it forms a valid word square.
A sequence of words forms a valid word square if thekthrow and column read the exact same string, where 0 ≤k< max(numRows, numColumns).
Note:
- The number of words given is at least 1 and does not exceed 500.
- Word length will be at least 1 and does not exceed 500.
- 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.
S: O(n*k)
注意edge case word过长或过短的处理
bool validWordSquare(vector<string>& words) {
int n = words.size();
for (int i = 0; i < n; ++i) {
for (int j = 0; j < words[i].size(); ++j) {
if (j >= n || words[j].size() <= i || words[i][j] != words[j][i]) return false;
}
}
return true;
}