iven a matrix of lower alphabets and a dictionary. Find all words in the dictionary that can be found in the matrix. A word can start from any position in the matrix and go left/right/up/down to the adjacent position.
Have you met this question in a real interview?
Yes
Example
Given matrix:
doaf
agai
dcan
and dictionary:
{"dog", "dad", "dgdg", "can", "again"}
return {"dog", "dad", "can", "again"}
dog:
do
af
a
g
ai
dcan
dad:
d
oaf
a
gai
d
can
can:
doaf
agai
d
can
again:
doaf
agai
dca
n
Using trie to implement your algorithm.
35 seach in vector using std::find
- 39 using node- > instead of node.
- 49 parameter
- 61 class public
- 32 struct need semicolon
class TrieNode {
public:
TrieNode\(\) {
IsEnd = false;
for \(int i = 0; i < 26; ++i\) {
next\[i\] = NULL;
}
}
TrieNode\* next\[26\];
bool IsEnd;
string word;
};
class Solution {
public:
/\*\*
\* @param board: A list of lists of character
\* @param words: A list of string
\* @return: A list of string
\*/
vector<string> wordSearchII\(vector<vector<char> > &board, vector<string> &words\) {
// write your code here
if \(words.empty\(\)\) {
return {};
}
TrieNode\* root = new TrieNode\(\);
for \(string& word : words\) {
insertWord\(root, word\);
}
vector<string> res;
int n = board.size\(\);
int m = board\[0\].size\(\);
for \(int i = 0; i < n; ++i\) {
for \(int j = 0; j < m; ++j\) {
vector<vector<bool>> f\(n, vector<bool>\(m, false\)\);
search\(board, i, j, root, f, res\);
}
}
return res;
}
void search\(vector<vector<char> > &board, int i, int j, TrieNode\* root, vector<vector<bool>> &f, vector<string>& res\) {
root = root->next\[board\[i\]\[j\] - 'a'\];
if \(f\[i\]\[j\] \|\| root == NULL\) {
return;
}
if \(root->IsEnd\) {
if \(find\(res.begin\(\), res.end\(\), root->word\) == res.end\(\)\) {
res.push\_back\(root->word\);
}
}
vector<vector<int>> offsets = {{1,0}, {-1,0}, {0,1}, {0,-1}};
f\[i\]\[j\] = true;
for \(auto& offset : offsets\) {
int x = i + offset\[0\];
int y = j + offset\[1\];
if \(!IsInside\(x, y, board.size\(\), board\[0\].size\(\)\)\) {
continue;
}
search\(board, x, y, root, f, res\);
}
f\[i\]\[j\] = false;
}
bool IsInside\(int x, int y, int n, int m\) {
return x >= 0 && x < n && y >= 0 && y < m;
}
void insertWord\(TrieNode\* root, string& word\) {
TrieNode\* p = root;
for \(int i = 0; i < word.length\(\); ++i\) {
int idx = word\[i\] - 'a';
if \(p->next\[idx\] == NULL\) {
p->next\[idx\] = new TrieNode\(\);
}
p = p->next\[idx\];
}
p->IsEnd = true;
p->word = word;
}
};