字典树算法



2020年9月29日 周二 天气晴 【不悲叹过去，不荒废现在，不惧怕未来】

直观想法是按照 LeetCode 79. 单词搜索（DFS+回溯）的思路，对中的每一个字符串都进行遍历，但是这样的话时间复杂度太高。我们可以借助字典树来简化搜索过程，具体思路是：对中的单词构建字典树——>从图中的每个位置出发 ——> 从字典树中，看遍历过程中是否遇到了 中的某个单词。

遍历过程需要解决几点问题：

1. 如何避免遍历时，字符被重复使用？
2. 如何获取符合条件的字符串？
3. 如何避免字符串的重复遍历？

第一个问题相对好解决，我们在 LeetCode 79. 单词搜索（DFS+回溯）中已经学会了如何解决这个问题，在不更改输入矩阵 的情况下，最好的办法是建立一个矩阵，将已经遍历过的字符标记为，遍历完4个方向再改为，因为后面可能还要用到这个字符。之所以在 LeetCode 79. 单词搜索（DFS+回溯）这题中，不建议将遍历过的字符修改成特殊字符然后再改回来，是因为一旦搜索到存在这个字符串，程序就会提前结束，修改成特殊字符的那些字符不会被修改回去，导致输入矩阵被我们人为改变了，这是需要极力避免的。但是在本题中，我们可以用修改成特殊字符的方法，原因是不论最后能不能找到需要的字符串，都能回溯回去还原字符。 这一点和 LeetCode 79. 单词搜索（DFS+回溯）不同，可以仔细对比一下两题的代码。

对于第二个问题，我们可以改进字典树，将换成，意思为如果以这个字符结尾能构成字符串，就设置为这个字符串，否则为空。 这样就方便存储符合条件的字符串了。

第三个问题解决后，第三个问题也就迎刃而解了，一旦发现符合条件的字符串，就保存下来，也就是，然后将设置为空，表明这个字符串已经被找到了，后面就不会再重复添加。

具体代码如下：

https://leetcode-cn.com/problems/word-search-ii/solution/c-jian-dan-qing-xi-de-trieshu-ti-jie-by-talanto_li/

https://leetcode-cn.com/problems/word-search-ii/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-44/

https://leetcode-cn.com/problems/word-search-ii/solution/dan-ci-sou-suo-ii-by-leetcode/

版权声明：

本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。

本文网址：https://www.mushiming.com/mjsbk/5586.html