Description:
Given 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.
Example
Given matrix:
doaf
agai
dcan
and dictionary:
{"dog", "dad", "dgdg", "can", "again"}
return {"dog", "dad", "can", "again"}
dog:
doaf
agai
dcan
dad:
doaf
agai
dcan
can:
doaf
agai
dcan
again:
doaf
agai
dcan
Solution:
class Solution {
private:
struct TrieNode {
TrieNode* next[26];
bool flag;
TrieNode() {
flag = false;
fill_n(next, 26, nullptr);
}
};
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
vector<string> rc;
auto m = (int)board.size();
if (m == 0) return rc;
auto n = (int)board[0].size();
if (n == 0) return rc;
auto sz = (int)words.size();
auto trie = new TrieNode();
for (int i = 0; i < sz; ++i) {
auto word = words[i];
auto node = trie;
for (int j = 0; j < word.length(); ++j) {
if (node->next[word[j]-'a']) {
node = node->next[word[j]-'a'];
} else {
node->next[word[j]-'a'] = new TrieNode();
node = node->next[word[j]-'a'];
}
}
node->flag = true;
}
string tmp;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
help(board, m, n, i, j, trie, rc, tmp);
}
}
return rc;
}
void help(vector<vector<char>>& board, int m, int n, int i, int j, TrieNode* node, vector<string>& res, string& tmp) {
if (!node) return;
if (node->flag) {
res.push_back(tmp);
node->flag = false;
}
if (i < 0 || i >= m || j < 0 || j >= n) return;
auto ch = board[i][j];
if (ch == '*') return;
board[i][j] = '*';
tmp.push_back(ch);
help(board, m, n, i+1, j, node->next[ch-'a'], res, tmp);
help(board, m, n, i-1, j, node->next[ch-'a'], res, tmp);
help(board, m, n, i, j+1, node->next[ch-'a'], res, tmp);
help(board, m, n, i, j-1, node->next[ch-'a'], res, tmp);
tmp.pop_back();
board[i][j] = ch;
}
};
转载于:https://www.cnblogs.com/deofly/p/word-search-ii.html
