csdn_muxin的博客

定制前缀树的查询方法解题

前缀树 + 双指针

题目来源：https://leetcode-cn.com/problems/concatenated-words/ 大致题意： 给定一个字符串数组，判断其中的长字符串能否由短字符串连接组成，返回能被短串组成的长串 思路 这波是前缀树（字典树）的搜索，老朋友换新衣服 既然要用短串组成长串，那么就需要先把短串插入字典树中，然后遇到长串就搜索 排序 + 前缀树 + DFS 构建前缀树类 将给定字符串数组排序，然后遍历字符串数组，遇到空串直接跳过 对于当前遍历的字符串，先在前缀树中搜索它是否可以由存入的字符串组成

题目来源：https://leetcode-cn.com/problems/design-add-and-search-words-data-structure/ 大致题意： 实现一个词典类： 有构造函数可以初始化 有 addWord(String word) 方法，可以添加一个单词到当前对象 有 search(String word) 方法，搜索当前对象中是否有该单词，若有返回 true，否则返回 false。word 中可能包含一些 ‘.’，每个 ‘.’ 可以表达任意字符 思路 使用前缀树进行单词

题目来源：208. 实现 Trie (前缀树)、212. 单词搜索 II 大致题意： 给定一个 m×n 的二维字符数组，和一个字符串数组。输出字符串数组中能由字符数组的连续字符组成的字符串。连续字符是指上下左右相邻的字符元素，在一个匹配中，一个字符元素只允许出现一次。 思路 本来我想的就是用 dfs，直接对字符串数组的每个元素，都对字符数组每个位置都进行 dfs，然后找到一个字符串就加进去答案。 理论上可行，但是写出来不对，而且很明显复杂度太高，就去看题解。 然后发现是用前缀树解题，我又不知道前缀树是什么，