波波老师求教word search2
来源：8-6 二维平面上的回溯法 Word Search
宝慕林3543342
2019-02-09
感觉听懂了word search结果一结合trie的word search2（leetcode 212） 又不会做了能不能求一个bobo老师的解法 (;´༎ຶД༎ຶ`)
另外想问一下如果对于word search这道题如果棋盘很大的话有什么更好的方式可以搜索一个单词呢？
2回答
-
试了一下，完全结合208号问题的Trie和79号的Word Search就可以过：）
我的参考代码（C++）：
https://github.com/liuyubobobo/Play-Leetcode/blob/master/0212-Word-Search-II/cpp-0212/main.cpp
整体思路是：
对所给出的单词列表建立一个Trie（87-91行），其中的Trie是208号问题的代码原封不动拿过来。
之后，对于当前棋盘的从每一个位置出发的每一条路径，判断这条路径上的字符串是否在trie中。（98-102行）
void searchWord(const vector<vector<char>> &board, Trie& trie, int x, int y, string s, vector<vector<bool>>& visited, unordered_set<string>& res)
这个函数进行整个搜索过程：
其中x和y是当前搜索的位置；
s是从起点到当前位置，所经过路径对应的字符串，我们每次就判断这个字符串是否在trie中，存储res中（115行）；
visited是便利中的标记，保证不走重复的格子；
具体搜索过程中，有两个小优化。
1）如果当前路径的字符串s，已经比单词列表中最长的单词还长了，就不用搜了（113行）
2）如果当前路径的字符串s，不是单词列表中任何单词的前缀，就不用搜了（114行）
整体搜索过程应该还可以有更多优化（114和115的判断明显在多次重复执行）。不过这个问题整体是个NP问题，使用的是回溯法，不会有多项式算法。加上更多优化目测要动Trie的代码了，在这里我就不继续优化了：）
相信你可以很容易的把以上解法转换为Java代码：）
加油！：）
112019-02-09 -
宝慕林3543342
提问者
2019-02-09
啊对了能不能厚颜无耻地求java的解法……
00
相似问题
回答 1
回答 1