Word Search II
最后更新于：2022-04-01 22:57:49
**一. 题目描述**
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"]`.
Note:
You may assume that all inputs are consist of lowercase letters `a-z`.
**二. 题目分析**
若沿用Word Search的方法，必定超时。
一种被广为使用的方法是使用字典树，网上的相关介绍不少，简单沿用一种说法，就是一种单词查找树，Trie树，属于树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。
其具体性质、查找方法等可参照：[http://baike.baidu.com/link?url=BR1qdZ2oa8BIRbgtD6_oVsaBhzRecDJ0MMFntUvPGNjpG3XgJZihyUdFAlw1Pa30-OFUsNJRWPSanHng65l-Ja](http://baike.baidu.com/link?url=BR1qdZ2oa8BIRbgtD6_oVsaBhzRecDJ0MMFntUvPGNjpG3XgJZihyUdFAlw1Pa30-OFUsNJRWPSanHng65l-Ja)
而具体的解题思路是：
1. 将待查找的单词储存在字典树Trie中，使用DFS在board中查找，利用字典树进行剪枝。
2. 每当找到一个单词时，将该单词从字典树中删去。
3. 返回结果按照字典序递增排列。
**三. 示例代码**
以下代码虽然使用字典树来改进dfs，但AC后发现算法还是比较耗时：
~~~
#include
#include
#include
#include
using namespace std;
class TrieNode
{
public:
TrieNode() // 构造函数
{
for (int i = 0; i < 26; ++i)
next[i] = NULL;
end = false;
}
void insert(string s)
{
if (s.empty())
{
end = true;
return;
}
if (next[s[0] - 'a'] == NULL)
next[s[0] - 'a'] = new TrieNode();
next[s[0] - 'a']->insert(s.substr(1)); // 右移一位截取字符串s，继续递归插入
}
bool search(string key)
{
if (key.empty())
return end;
if (next[key[0] - 'a'] == NULL)
return false;
return next[key[0] - 'a']->search(key.substr(1));
}
bool startsWith(string prefix)
{
if (prefix.empty())
return true;
if (next[prefix[0] - 'a'] == NULL)
return false;
return next[prefix[0] - 'a']->startsWith(prefix.substr(1));
}
private:
TrieNode *next[26];
bool end;
};
class Tri
{
public:
Tri(){
root = new TrieNode();
}
void insert(string s)
{
root->insert(s); // 调用TrieNode类的方法
}
bool search(string k)
{
return root->search(k);
}
bool startsWith(string p)
{
return root->startsWith(p);
}
private:
TrieNode *root;
};
class Solution
{
public:
vector findWords(vector>& board, vector& words)
{
const int x = board.size();
const int y = board[0].size();
for (auto ptr : words)
tree.insert(ptr); // 将候选单词插入字典树中
vector result;
for (int i = 0; i < x; ++i)
{
for (int j = 0; j < y; ++j)
{
// 用于记录走过的路径
vector > way(x, vector(y, false));
dfs(board, way, "", i, j, result);
}
}
// 以下操作排除重复出现的单词
sort(result.begin(), result.end());
result.erase(unique(result.begin(), result.end()), result.end());
return result;
}
private:
Tri tree;
void dfs(vector > &board, vector > way, string word, int x, int y, vector &result)
{
if (x < 0 || x >= board.size() || y < 0 || y >= board[0].size()) // 超出边界
return;
if (way[x][y])
return;
word.push_back(board[x][y]);
if (tree.search(word))
result.push_back(word);
if (tree.startsWith(word))
{
way[x][y] = true;
dfs(board, way, word, x + 1, y, result);
dfs(board, way, word, x - 1, y, result);
dfs(board, way, word, x, y + 1, result);
dfs(board, way, word, x, y - 1, result);
way[x][y] = false;
}
word.pop_back();
}
};
~~~
以下是网上一种使用字典树的算法，耗时48ms - 56ms：
~~~
class Trie {
public:
Trie *next[26];
bool exist;
Trie() {
fill_n(next, 26, nullptr);
exist = false;
}
~Trie() {
for (int i = 0; i < 26; ++i)
delete next[i];
}
void insert(const string &t) {
Trie *iter = this;
for (int i = 0; i < t.size(); ++i) {
if (iter->next[t[i] - 'a'] == nullptr)
iter->next[t[i] - 'a'] = new Trie();
iter = iter->next[t[i] - 'a'];
}
iter->exist = true;
}
};
class Solution {
public:
int m, n;
vector findWords(vector>& board, vector& words) {
Trie *trie = new Trie();
for (auto &s : words)
trie->insert(s);
m = board.size();
n = board[0].size();
vector ret;
string sofar;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
bc(board, ret, sofar, trie, i, j);
}
}
return ret;
}
void bc(vector> &board, vector &ret, string &sofar, Trie *root, int x, int y) {
if (x < 0 || y < 0 || x >= m || y >= n || board[x][y] == '\0' || root == nullptr)
return ;
if (root->next[board[x][y] - 'a'] == nullptr)
return ;
root = root->next[board[x][y] - 'a'];
char t = '\0';
swap(t, board[x][y]);
sofar.push_back(t);
if (root->exist) {
root->exist = false;
ret.push_back(sofar);
}
bc(board, ret, sofar, root, x, y + 1);
bc(board, ret, sofar, root, x + 1, y);
bc(board, ret, sofar, root, x - 1, y);
bc(board, ret, sofar, root, x, y - 1);
swap(t, board[x][y]);
sofar.pop_back();
}
};
~~~
**四. 小结**
学习并初次使用了字典树，并不是十分熟悉，写出的代码计算比较耗时。
';