题目描述（困难难度）

79 题 Word Search 的延续。

意思就是从某个字符出发，然后它可以向左向右向上向下移动，走过的路径构成一个字符串，判断是否能走出给定字符串的 word ，还有一个条件就是走过的字符不能够走第二次。

比如 eat，从第二行最后一列的 e 出发，向左移动，再向左移动，就走出了 eat。

题目中给一个 word 列表，要求找出哪些单词可以由生成。

解法一

直接利用 79 题的代码，79 题是判断某个单词能否在 board 中生成。这里的话，很简单，直接遍历 words 数组，然后利用 79 题的代码去依次判断即可。

使用的时候采用 dfs ，没做过的话大家可以先过去看一下。

然后它竟然过了，竟然过了。。。我还以为这么暴力一定会暗藏玄机。不过为了尊重它是一道 hard 的题目，我就继续思考能不能优化下。

顺着上边的思路想，首先 79 题中判断单个单词是否能生成肯定不能优化了，不然之前肯定会写优化方法。那么继续优化的话，就只能去寻求不同 word 的之间的联系了。

什么意思呢？

或者知道了某个单词不能生成，对于后边将要判断的单词能不能提供些帮助呢？

想了想，只想到了一种情况。比如我们已经知道了 basketboard 能够在二维数组 board 中生成。那么它的所有前缀一定也能生成，比如 basket 一定能够生成。

说到前缀，自然而然的想到了之前的前缀树，这几天出现的频率也比较高，刚做的也用到了。我们可以把能生成的 word 加入到前缀树中，然后再判断后边的单词前，先判断它是不是前缀树中某个单词的前缀。

当然如果单词是 B 的前缀，那么 A 的长度肯定短一些，所以我们必须先判断了较长的单词 B，才能产生优化的效果。所以我们首先要把 words 按照单词的长度从大到小排序。

小弟不才，只想到了这一种联系，下边是代码，前缀树直接搬 208 题的代码即可。

然而事实是残酷的，对于 leetcode 的 test cases ，这个想法并没有带来速度上的提升。于是就去逛 discuss 了，也就是下边的解法二。

参考这里)。

解法一中的想法是， -> 从图中的每个位置出发，看能否找到这个单词

我们其实可以倒过来。从图中的每个位置出发 -> 看遍历过程中是否遇到了 words 中的某个单词

至于实现的话，我们可以在遍历过程中，将当前路径的单词传进函数，然后判断当前路径构成的单词是否是在前缀树中出现即可。

这个想法可行，但不够好，因为每次都从前缀树中判断当前路径的单词，会带来重复的判断。比如先判断了 an 存在于前缀树中，接下来假如路径变成 ang ，判断它在不在前缀中，又需要判断一遍 an 。

因此，我们可以将前缀树融合到我们的算法中，递归中去传递前缀树的节点，判断当前节点的孩子是否为 null，如果是说明当前前缀不存在，可以提前结束。如果不是 null，再判断当前节点是否是单词的结尾，如果是结尾直接将当前单词加入。

由于递归过程中没有加路径，所以我们改造一下前缀树的节点，将单词直接存入节点，这样的话就可以直接取到了。

干巴巴的文字可能不好理解，看一下下边的代码应该就明白了。

结合代码就很好懂了，就是从每个位置对图做深度优先搜索，然后路径生成的字符串如果没有在前缀树中出现就提前结束，如果到了前缀树中某个单词的结束，就将当前单词加入即可。

受到前边的题目思维的限制，只想到了解法一，优化的话也没有很成功。其实把思路倒过来，解法二也就可以出来了，很有意思。

添加好友一起进步~

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击这里查看详情