[Leetcode 212] Word Search II

作者 Shilei Tian 日期 2017-01-11
[Leetcode 212] Word Search II

题目要求

Given a 2D board and a list of words from the dictionary, find all words in the board.

Each word must be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

For example,

Given words = ["oath","pea","eat","rain"] and board =

[

[‘o’,’a’,’a’,’n’],

[‘e’,’t’,’a’,’e’],

[‘i’,’h’,’k’,’r’],

[‘i’,’f’,’l’,’v’]

]

Return ["eat","oath"].

解题思路

这道题很容易就利用 79. Word Search 的思路来做,检查每一个 word,判断是否存在,代码如下:

class Solution {
public:
vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
vector<string> ret;
for (const auto& word : words) {
if (find(ret.begin(), ret.end(), word) != ret.end()) {
continue;
}
if (exist(board, word)) {
ret.push_back(word);
}
}
return ret;
}
private:
bool exist(vector<vector<char>>& board, const string& word) {
if (board.size() == 0 || board[0].size() == 0 || word.size() == 0 || word.size() > board.size() * board[0].size()) {
return false;
}
for (int i = 0; i < board.size(); ++i) {
for (int j = 0; j < board[0].size(); ++j) {
if (search(board, word, 0, i, j)) {
return true;
}
}
}
return false;
}
bool search(vector<vector<char>>& board, const string& word, const int p, const int x, const int y) {
if (p == word.size()) {
return true;
} else if (x < 0 || y < 0 || x == board.size() || y == board[0].size() || board[x][y] != word[p]) {
return false;
}
char tmp = board[x][y];
board[x][y] = 0;
bool res = search(board, word, p + 1, x - 1, y) || search(board, word, p + 1, x + 1, y)
|| search(board, word, p + 1, x, y - 1) || search(board, word, p + 1, x, y + 1);
board[x][y] = tmp;
return res;
}
};

但是,提交时候会发现超时。这个时候观察测试样例,会发现很多前缀一样的单词,但是我们对于每一个单词都从头检查,因此效率比较低。那么我们应该如何做才能将前缀考虑进去呢?

既然我们这里提到了前缀,并且想要将前缀考虑进去,那么之前我们在 Maximum XOR Of Two Numbers In An Array 中讲过的 Trie 是再合适不过的了。我们可以先对整个序列建立一个 Trie,接下来就是思路不同的地方了。我们上面是用每个单词的每个字母来查找从一个位置下一跳的位置,这样递归地查找。而有了 Trie 以后,我们可以遍历 board 上所有可能组成的 word,然后再检查这个 word 是否在 Trie 中,如果是,那么就说明我们可以找到,否则,就不在。代码如下:

class Solution {
public:
vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
vector<string> ret;
TrieNode* root = buildTrie(words);
for (int i = 0; i < board.size(); ++i) {
for (int j = 0; j < board[i].size(); ++j) {
search(root, board, i, j, ret);
}
}
return ret;
}
private:
struct TrieNode {
TrieNode* next[26];
string str;
};
TrieNode* buildTrie(const vector<string>& words) {
TrieNode* root = new TrieNode();
for (const auto& word : words) {
TrieNode* p = root;
for (const auto ch : word) {
auto offset = ch - 'a';
if (p->next[offset] == nullptr) {
p->next[offset] = new TrieNode();
}
p = p->next[offset];
}
p->str = word;
}
return root;
}
void search(const TrieNode* root, vector<vector<char>> board, const int x, const int y, vector<string>& res) {
auto offset = board[x][y] - 'a';
if (board[x][y] == '#' || root->next[offset] == nullptr) {
return;
}
const auto next = root->next[offset];
if (!next->str.empty()) {
res.push_back(next->str);
next->str.clear();
}
char tmp = board[x][y];
board[x][y] = '#';
if (x > 0) {
search(next, board, x - 1, y, res);
}
if (x + 1 < board.size()) {
search(next, board, x + 1, y, res);
}
if (y > 0) {
search(next, board, x, y - 1, res);
}
if (y + 1 < board[x].size()) {
search(next, board, x, y + 1, res);
}
board[x][y] = tmp;
}
};