波波老师求教word search2

Question

感觉听懂了word search结果一结合trie的word search2（leetcode 212） 又不会做了能不能求一个bobo老师的解法 (;´༎ຶД༎ຶ`)
另外想问一下如果对于word search这道题如果棋盘很大的话有什么更好的方式可以搜索一个单词呢？

Answer 1

liuyubobobo 2019-02-09 09:34:33

试了一下，完全结合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代码：）

加油！：）

• 提问者 宝慕林3543342 #1

  啊啊啊！！！谢谢波波老师！！！

Answer 2

提问者 宝慕林3543342 2019-02-09 08:20:46

啊对了能不能厚颜无耻地求java的解法……