**一. 题目描述**
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 <iostream>
#include <vector>
#include <string>
#include <algorithm>
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<string> findWords(vector<vector<char>>& board, vector<string>& words)
{
const int x = board.size();
const int y = board[0].size();
for (auto ptr : words)
tree.insert(ptr); // 将候选单词插入字典树中
vector<string> result;
for (int i = 0; i < x; ++i)
{
for (int j = 0; j < y; ++j)
{
// 用于记录走过的路径
vector<vector<bool> > way(x, vector<bool>(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<vector<char> > &board, vector<vector<bool> > way, string word, int x, int y, vector<string> &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<string> findWords(vector<vector<char>>& board, vector<string>& words) {
Trie *trie = new Trie();
for (auto &s : words)
trie->insert(s);
m = board.size();
n = board[0].size();
vector<string> 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<vector<char>> &board, vector<string> &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();
}
};
~~~
**四. 小结**
学习并初次使用了字典树，并不是十分熟悉，写出的代码计算比较耗时。
- 前言
- 2Sum
- 3Sum
- 4Sum
- 3Sum Closest
- Remove Duplicates from Sorted Array
- Remove Duplicates from Sorted Array II
- Search in Rotated Sorted Array
- Remove Element
- Merge Sorted Array
- Add Binary
- Valid Palindrome
- Permutation Sequence
- Single Number
- Single Number II
- Gray Code（2016腾讯软件开发笔试题）
- Valid Sudoku
- Rotate Image
- Power of two
- Plus One
- Gas Station
- Set Matrix Zeroes
- Count and Say
- Climbing Stairs（斐波那契数列问题）
- Remove Nth Node From End of List
- Linked List Cycle
- Linked List Cycle 2
- Integer to Roman
- Roman to Integer
- Valid Parentheses
- Reorder List
- Path Sum
- Simplify Path
- Trapping Rain Water
- Path Sum II
- Factorial Trailing Zeroes
- Sudoku Solver
- Isomorphic Strings
- String to Integer (atoi)
- Largest Rectangle in Histogram
- Binary Tree Preorder Traversal
- Evaluate Reverse Polish Notation（逆波兰式的计算）
- Maximum Depth of Binary Tree
- Minimum Depth of Binary Tree
- Longest Common Prefix
- Recover Binary Search Tree
- Binary Tree Level Order Traversal
- Binary Tree Level Order Traversal II
- Binary Tree Zigzag Level Order Traversal
- Sum Root to Leaf Numbers
- Anagrams
- Unique Paths
- Unique Paths II
- Triangle
- Maximum Subarray（最大子串和问题）
- House Robber
- House Robber II
- Happy Number
- Interlaving String
- Minimum Path Sum
- Edit Distance
- Best Time to Buy and Sell Stock
- Best Time to Buy and Sell Stock II
- Best Time to Buy and Sell Stock III
- Best Time to Buy and Sell Stock IV
- Decode Ways
- N-Queens
- N-Queens II
- Restore IP Addresses
- Combination Sum
- Combination Sum II
- Combination Sum III
- Construct Binary Tree from Inorder and Postorder Traversal
- Construct Binary Tree from Preorder and Inorder Traversal
- Longest Consecutive Sequence
- Word Search
- Word Search II
- Word Ladder
- Spiral Matrix
- Jump Game
- Jump Game II
- Longest Substring Without Repeating Characters
- First Missing Positive
- Sort Colors
- Search for a Range
- First Bad Version
- Search Insert Position
- Wildcard Matching