原题描述
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.
Trie+回溯算法
使用BoardFlag来标识该点有没有被遍历过
在回溯搜索时先进行合法性检测，主要检测如下：
- 当前点遍历过，则返回false，不再接着搜索，开始回溯
- 在words字典中没有以 当前字符串 为前缀的word，则返回false，不再搜索，开始回溯
- 若words字典中含有 当前字符串 的word，并且没有输出过，则保存到输出列表里
- 返回true，继续搜索
回溯搜索的过程如下：
- 先进行合法性检测，判断需不需要进一步搜索
- 若不需要搜索，直接进行回溯
- 若需要搜索，则将当前位置的BoardFlag置位，以Flag遍历过，把相应的字典树前进一位，并保存搜索到目前为止的当前字符串
- 进一步递归搜索上、下、左、右4个位置，需要边界检查
- 搜索完了之后清空相应的BoardFlag标志位，开始回溯
主程序需要完成以下工作：
- 异常检测
- 初始化Trie字典树
- 初始化BoardFlag标志位
- 遍历Board上的所有起点，然后对于每一个起点做回溯搜索
C++代码
typedef struct trieNode {
struct trieNode* next[26];
bool valid;
bool output;
}TrieNode, *Trie;
TrieNode* createTrieNode() {
TrieNode* node = (TrieNode*)malloc(sizeof(TrieNode));
node->valid = false;
node->output = true;
memset(node->next, NULL, sizeof(node->next));
return node;
}
void insertWord(Trie root, string word) {
if (word.length() <= 0) {
return;
}
int len = word.length();
for (int i = 0; i < len; i++) {
if (root->next[word[i] - 'a'] == NULL) {
root->next[word[i] - 'a'] = createTrieNode();
}
root = root->next[word[i] - 'a'];
}
root->valid = true;
}
class Solution {
public:
Trie root = createTrieNode();
vector<string> ret;
vector<vector<bool>> boardFlag;
vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
for (int i = 0; i < words.size(); i++) {
insertWord(root, words[i]);
}
if (board.size() <= 0) {
return ret;
}
for (int i = 0; i < board.size(); i++) {
vector<bool> tempFlag;
for (int j = 0; j < board[0].size(); j++) {
tempFlag.push_back(false);
}
boardFlag.push_back(tempFlag);
}
for (int i = 0; i < board.size(); i++) {
for (int j = 0; j < board[0].size(); j++) {
string str = "";
backTrace(root, i, j, str, board);
}
}
return ret;
}
void backTrace(Trie p, int i, int j, string str, vector<vector<char>>& board) {
bool stop = !check(p, i, j, str, board);
int maxI = boardFlag.size() - 1;
int maxJ = boardFlag[0].size() - 1;
if (!stop) {
boardFlag[i][j] = true;
p = p->next[board[i][j] - 'a'];
str += board[i][j];
if (i + 1 <= maxI) {
backTrace(p, i + 1, j, str, board);
}
if (i - 1 >= 0) {
backTrace(p, i - 1, j, str, board);
}
if (j + 1 <= maxJ) {
backTrace(p, i, j + 1, str, board);
}
if (j - 1 >= 0) {
backTrace(p, i, j - 1, str, board);
}
boardFlag[i][j] = false;
}
}
bool check(Trie p, int i, int j, string str, vector<vector<char>>& board) {
if (boardFlag[i][j]) {
return false;
}
if (p->next[board[i][j] - 'a'] == NULL) {
return false;
}
p = p->next[board[i][j] - 'a'];
str += board[i][j];
if (p->valid && p->output) {
p->output = false;
ret.push_back(str);
}
return true;
}
};