LintCode-132: Word Search II (DFS深搜经典难题!）

132. Word Search II
     中文English
     Given a matrix of lower alphabets and a dictionary. Find all words in the dictionary that can be found in the matrix. A word can start from any position in the matrix and go left/right/up/down to the adjacent position. One character only be used once in one word. No same word in dictionary

Example
Example 1:

Input：[“doaf”,“agai”,“dcan”]，[“dog”,“dad”,“dgdg”,“can”,“again”]
Output：[“again”,“can”,“dad”,“dog”]
Explanation：
d o a f
a g a i
d c a n
search in Matrix，so return [“again”,“can”,“dad”,“dog”].
Example 2:

Input：[“a”]，[“b”]
Output：[]
Explanation：
a
search in Matrix，return [].
Challenge
Using trie to implement your algorithm.

解法1：
这题挺难的。我参考的网上的答案。
思路就是暴力深搜 - 每个格子来一次DFS深搜。
注意：

1. visited[]数组还是需要
2. 注意剪枝：如果不是prefix，剪掉！ 如果出界或已经访问过，剪掉！
3. char -> string 不能直接用std里面的to_string()，因为char本来就是integer，to_string(char)会生成"100","103"这样的字符串。可以用string(1,c)来生成一个临时的内容为c，长度为1的字符串。
4. 对于二维数组或vector，用if (board.size() < 1) 比if (board.empty()) 更好
5. getPrefixSets()里面，下面一行
   if (prefixSets.find(prefix) == prefixSets.end())
   很关键！因为有可能某个word刚好是之前某个prefix，这样可以避免该word被关联到false！

class Solution {
public:/*** @param board: A list of lists of character* @param words: A list of string* @return: A list of string*/vector dx = {0, 1, -1, 0};vector dy = {1, 0, 0, -1};map prefixSets; //放所有的prefix，如果是word就对应true，否则对应falsevector wordSearchII(vector> &board, vector &words) {vector result;if (board.size() < 1)  //比if (board.empty()) 更好？return result;vector> visited;for (int i = 0; i < board.size(); ++i) visited.push_back(vector(board[i].size(), false));getPrefixSets(words);set wordSet;for (int i = 0; i < board.size(); ++i) {for (int j = 0; j < board[i].size(); ++j) {visited[i][j] = true;//char->string 不可以用to_string,否则就是 100->"100"helper(board, visited, i, j, string(1, board[i][j]), wordSet); //注意string(1,c)visited[i][j] = false;}}for (auto w : wordSet)result.push_back(w);return result;}private://generate the mapvoid getPrefixSets(vector &words) {for (auto w : words) {for (int i = 0; i < w.size() - 1; ++i) {  //不需要到w.size()，因为整个word下面会处理string prefix = w.substr(0, i + 1); //前i + 1个字符if (prefixSets.find(prefix) == prefixSets.end()) //关键！有可能某个word刚好是之前某个prefix，这样可以避免该word被关联到false！prefixSets[prefix] = false;}prefixSets[w] = true;}}void helper(vector> &board, vector> &visited, int x, int y, string word, set &wordSet) {if (prefixSets.find(word) == prefixSets.end())  //如果不是prefix, 剪枝return;if (prefixSets[word]) wordSet.insert(word);for (int i = 0; i < 4; ++i) {int adjX = x + dx[i];int adjY = y + dy[i];if (!inside(board, adjX, adjY) || visited[adjX][adjY])  // 出界或已访问，剪枝continue;visited[adjX][adjY] = true;helper(board, visited, adjX, adjY, word + board[adjX][adjY], wordSet);visited[adjX][adjY] = false;}}bool inside(vector> &board, int x, int y) {return x >= 0 &&x < board.size() &&y >= 0 &&y < board[0].size();}        
};

二刷:

class Solution {
public:/*** @param board: A list of lists of character* @param words: A list of string* @return: A list of string*          we will sort your return value in output*/vector<string> wordSearchII(vector<vector<char>> &board, vector<string> &words) {unordered_set<string> wordSets;unordered_set<string> preSets;for (auto word : words) {string pre = "";for (int i = 0; i < word.size(); i++) {pre = pre + word[i];preSets.insert(pre);}wordSets.insert(pre);}unordered_set<string> sols;for (int i = 0; i < board.size(); i++) {for (int j = 0; j < board[0].size(); j++) {vector<vector<bool>> visited(board.size(), vector<bool>(board[0].size(), false));string sol(1, board[i][j]);visited[i][j] = true;helper(board, wordSets, preSets, i, j, visited, sol, sols);visited[i][j] = false;sol.pop_back();}}vector<string> res(sols.begin(), sols.end());return res;}
private:void helper(vector<vector<char>> &board, unordered_set<string> &wordSets, unordered_set<string> &preSets,int currX, int currY, vector<vector<bool>> &visited, string sol, unordered_set<string> &sols) {if (preSets.find(sol) == preSets.end()) return;                if (wordSets.find(sol) != wordSets.end() && sols.find(sol) == sols.end()) {sols.insert(sol);//    return;  //do not stop! continue to search}for (int i = 0; i < 4; i++) {int newX = currX + dx[i];int newY = currY + dy[i];if (newX < 0 || newX >= board.size() ||newY < 0 || newY >= board[0].size() ||visited[newX][newY]) continue;//sol = sol + board[newX][newY];if (preSets.find(sol) != preSets.end()) {visited[newX][newY] = true;helper(board, wordSets, preSets, newX, newY, visited, sol + board[newX][newY], sols);visited[newX][newY] = false;//sol.pop_back();  //important} //else {//    sol.pop_back();//}}return;}int dx[4] = {0, 0, -1, 1};int dy[4] = {-1, 1, 0, 0};
};

解法2：trie+dfs

struct Node {Node *ch[26];string str;Node() {for (int i = 0; i < 26; i++) {ch[i] = nullptr;}str = "";}
};class Solution {
public:/*** @param board: A list of lists of character* @param words: A list of string* @return: A list of string*          we will sort your return value in output*/vector<string> wordSearchII(vector<vector<char>> &board, vector<string> &words) {Node *trieRoot = new Node();for (auto word : words) {insert(trieRoot, word);}unordered_set<string> sols;for (int i = 0; i < board.size(); i++) {for (int j = 0; j < board[0].size(); j++) {vector<vector<bool>> visited(board.size(), vector<bool>(board[0].size(), false));if (trieRoot->ch[board[i][j] - 'a'] != nullptr) {visited[i][j] = true;search(board, trieRoot->ch[board[i][j] - 'a'], i, j, visited, sols);visited[i][j] = false;}}}vector<string> res(sols.begin(), sols.end());return res;}
private:void insert(Node *p, string s) {int len = s.size();for (int i = 0; i < len; i++) {if (p->ch[s[i] - 'a'] == nullptr) {p->ch[s[i] - 'a'] = new Node();}p = p->ch[s[i] - 'a'];}p->str = s; //store the string at the last node// cout << " insert " << p->str << endl;}void search(vector<vector<char>> &board, Node *node, int x, int y, vector<vector<bool>> &visited, unordered_set<string> &sols) {if (!node->str.empty()) {sols.insert(node->str);//p->str = "";    //can also clear p->str here so there would be no duplicate //(i.e., we do not need to use set or unordered_set, vector sols is OK)}for (int i = 0; i < 4; i++) {int newX = x + dx[i];int newY = y + dy[i];if (newX < 0 || newX >= board.size() || newY < 0 || newY >= board[0].size() || visited[newX][newY]) continue;if (node->ch[board[newX][newY] - 'a'] != nullptr) {visited[newX][newY] = true;search(board, node->ch[board[newX][newY] - 'a'], newX, newY, visited, sols);visited[newX][newY] = false;}}}int dx[4] = {1, -1, 0, 0};int dy[4] = {0, 0, 1, -1};
};

注意：

1. 排重。否则下面的输入例子会有两个"dad"。
   Explanation：
   d o a f
   a g a i
   d c a n
   排重可用set或unordered_set，然后再将结果传给一个vector返回。也可以在得到一个node->str后，将node->str设为""，这样下一次就不会再得到这个node->str。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！