给定一个二维网格 board 和一个字典中的单词列表 words,找出所有同时在二维网格和字典中出现的单词。
单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。
示例:
输入:
words = ["oath","pea","eat","rain"] and board =
[
['o','a','a','n'],
['e','t','a','e'],
['i','h','k','r'],
['i','f','l','v']
]
输出: ["eat","oath"]
说明:
你可以假设所有输入都由小写字母 a-z 组成。
代码
class Solution {
public:
struct TrieNode {
TrieNode *child[26];
string str;
TrieNode() : str("") {
for (auto &a : child) a = NULL;
}
};
struct Trie {
TrieNode *root;
Trie() : root(new TrieNode()) {}
void insert(string s) {
TrieNode *p = root;
for (auto &a : s) {
int i = a - 'a';
if (!p->child[i]) p->child[i] = new TrieNode();
p = p->child[i];
}
p->str = s;
}
};
vector<string> findWords(vector<vector<char> >& board, vector<string>& words) {
vector<string> res;
if (words.empty() || board.empty() || board[0].empty()) return res;
vector<vector<bool> > visit(board.size(), vector<bool>(board[0].size(), false));
Trie T;
for (auto &a : words) T.insert(a);
for (int i = 0; i < board.size(); ++i) {
for (int j = 0; j < board[i].size(); ++j) {
if (T.root->child[board[i][j] - 'a']) {
search(board, T.root->child[board[i][j] - 'a'], i, j, visit, res);
}
}
}
return res;
}
void search(vector<vector<char> > &board, TrieNode *p, int i, int j, vector<vector<bool> > &visit, vector<string> &res) {
if (!p->str.empty()) {
res.push_back(p->str);
p->str.clear();
}
int d[][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
visit[i][j] = true;
for (auto &a : d) {
int nx = a[0] + i, ny = a[1] + j;
if (nx >= 0 && nx < board.size() && ny >= 0 && ny < board[0].size() && !visit[nx][ny] && p->child[board[nx][ny] - 'a']) {
search(board, p->child[board[nx][ny] - 'a'], nx, ny, visit, res);
}
}
visit[i][j] = false;
}
};