技术提高是一个循序渐进的过程，所以我讲的leetcode算法题从最简单的level开始写的，然后> 到中级难度，最后到hard难度全部完。目前我选择C语言，Python和Java作为实现语言，因为这三种语言还是比较典型的。由于篇幅和> 精力有限，其他语言的实现有兴趣的朋友请自己尝试。初级难度说的差不多的时候，我打算再加点其他内容，我可能会从操作系统到协议栈，从分布式> 聊到大数据框架，从大数据聊到人工智能，... ...。

如果有任何问题可以在文章后评论或者私信给我。

持续更新，敬请关注。

LeetCode 720. 字典中最长的字符(Longest Word in Dictionary)

问题描述：

给出一个表示英语词典的字符串列表words，找出words中可以由单词中的其他单词一次一个字符一次一个字符组合成的单词中最长的那一个词。如果有多个可能的答案，则返回字母序列最小的最长单词。

注：

• 输入中的所有字符串仅包含小写字母。
• words长度在区间[1, 1000]内。
• 字符串words[i]的长度在区间[1, 30]内。

示例：

C语言实现：

我给出两种解题方法。

第一种。排序

如果你在面试的时候遇到这个笔试题，建议用这个方法。

简单描述就是先对words进行排序，建议按照长度排序，这样可以减少不少计算量，如果按照ASCii字符排序.开销会比较大。

然后定义一个集合s和一个字符串对象res。

遍历排序后的words，对于每一个单词w，如果满足如下两个条件的就将其添加到s中：

• 长度是1；
• w去掉最后一个字符后形成的子串在s中存在；

因为words中可能有重复的字符串，所以我们s定义为集合，就是为了去重。

如果w可以添加到s中，就说明w是有可能作为满足题目条件的字符串被返回的。具体哪个单词可以返回，我们可以根据下面两个条件来筛选：

• 如果w比上一个潜在字符串长(上一个潜在字符串存储在res中)；
• 如果w和res一样长，按照字符顺序比较两个字符串；

随着遍历结束，res中保存的一定是字母序列最小的最长单词。

这里注意一个小细节，可以大大影响程序性能，题目对words的限制条件是，每个字符串的长度都不超过30，但是words可能有1000个字符串。所以我们在遍历排序后的words，如果长度超过30，可以直接忽略掉，因为一定不满足条件。

代码可以参考python的实现

第二种。前缀树(Tire tree)

其实这道题是一个典型的关于前缀树的题。实现起来会有些复杂，不建议笔试的时候这样做。

对于树的节点Node，我们定义如下：

它包含一个char类型字符。存储分拆的字符；一个Node指针数组children，存储接下来的Node节点(如果存在的话)，其长度是26，对于26个小写字母；另外还有一个字符串str，如果当前字符是单词w的最后一个字符，那么str会赋值为w。

Node形象化的描述，见后面的图示。

next指针以及AllocedNode会在后面描述。

我们可以定义一个空节点作为前缀树的根节点，然后对于words中的每一个单词字符串w，分拆成一个个字符，按顺序添加到前缀树中。

前缀树的插入和搜索函数定义如下：

在insert函数中，从前缀树的根节点开始，对单词s顺序遍历：

代码21~23行，如果，当前字符在树中的相遇位置节点为空，那么创建一个新的节点，完成赋值后添加到树中这个位置，同时，该新节点将作为一个新的起始位置开始遍历下一个字符；

代码27行，如果当前字符在树中的相应位置节点存在，那么该节点会作为新的起始位置开始遍历下一个字符；

代码29行，如果当前字符是单词的最后一个字符，或者说当前单词遍历结束，那么对赋值当前节点的str为当前单词，这个上面说过了。

我们会注意到，如果一个节点str是空的，说明在words中不存在以该节点作为结尾字符的单词，所以在查找的时候，遇到这样的节点，就没必要继续查找了。

插入的示图如下 （其中绿色表示新建Node节点，橙色表示对已有节点str值的更新）：

在search函数中，从树的节点n开始对其进行深度优先遍历，我们是用递归的方式来实现的。对于每一个节点，我们先定义一个变量res，初始为当前节点的str，如果str为空，则初始化为空字符串。

然后遍历它的所有的孩子数组children，如果某一个孩子是非空的且孩子的str也非空，那就递归调用search找到该孩子下面存储的最大的str，返回给t，然后比较t和res以确定哪个更应该作为返回的字符串。

如果你观察递归的回溯过程，你可能会觉得，t和res的比较好像有些多余，因为深度越大的元素,str往往比深度小的元素的str要长，但是其实比较是不可缺少的，因为在当前子树中它是最长的，不代表它在树的所有子树中都是最长的。

搜索的示图如下（红色虚线表示递归回溯的过程）：

在给定的接口函数longestWord中：

代码48,49行，我们先定义一个前缀树节点，memset很重要。

代码51，52行，完成前缀树的构建。

代码54。从根节点开始，查找整个树，找到符合条件的字符串。

内存管理

算法的整个过程中要创建很多Node对象，程序结束的时候我们须要释放它们。

在之前的一些题目中，遇到内存释放的时候，我们都是用数组的方式来存储待释放对象，那是因为在那些问题中，那些对象的数量通常是可以预估的，且有限的。但这这道题中，Node的数量不好估计，可能会非常多。

所以我们定义了一个AllotedNode结构来存储已分配的节点信息。它包含两个Node指针元素:

• tail 指针存储最新被分配的Node节点指针；
• list 指针存储第一个被分配的Node节点指针；

在Node节点中我们定义了一个next指针，这样可以让我们将所有已分配的Node对象链接起来，形成一个链表。

而tail指针的作用就是用于快速将Node对象插入到这个链表中（请看代码的第20，24, 25行）；

由于list指针总是指向这个链表的开头，所以我们可以通过从list开始遍历这个链表来释放所有的Node对象（请看代码57~62行）。

Java语言实现：

Java 的实现和C语言的实现一致，只是少了内存管理的部分，不再撰述。代码如下：

Python语言实现：

Python 是用上面方法一的排序来实现的，描述见上面，不再撰述。代码如下：