本文主要是介绍淼淼刷力扣，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

【努力刷力扣】第二十五天 --- 前缀树（trie树或者字典树）

• 引言
• 老样子，先看看题目要求：
• 利用循环模拟DFS过程
• • 整体思路：
  • • 1、针对字典树，我们可以这样理解（先看图）：
    • • 第一：
      • 第二:
      • 第三：
      • 第四：
  • 具体代码（内附注释）
• SumUp

引言

本人初次尝试写博客，希望各位看官大佬多多包容
有错误希望巨巨们提出来，我一定会及时改正，谢谢大家
在自己最好的年纪，找到了未来的目标
还有1年奋斗刷题，明年去面试实习，加油！

老样子，先看看题目要求：

注：该题出现频率较高，非常的重要。这个只是前缀树的一个基本模板，前缀树的操作无非就这几个，这种树有很强的应用价值，但是都逃不开这几个基础操作，都是在这个基础之上变形出来的。

利用循环模拟DFS过程

整体思路：

1、针对字典树，我们可以这样理解（先看图）：

第一：

有一个高高在上的"皇帝"，即根节点，所有所有的单词都是连在它后面的。

第二:

因为共有26个小写英文字母组成的单词，所以我并不清楚到底26个中到底谁来了，所以准备26个儿子（其实本质上是一样的，把二叉树推广到26叉而已，也并不一定全会用到，来谁就用谁），并且每个字母是通过"该字母 - ‘a’ "所得到的映射值，存到相应位置的，并没有存字母实体，利用这种映射即可解决

第三：

必须设置一个完整的单词录入结束的标志。

第四：

并不是所有儿子节点都有意义，存单词的儿子节点才有用

（上图红色节点代表一个单词的结束位置）

具体代码（内附注释）

注：

class Trie {//树在私有成员部分
public:
	/** Initialize your data structure here. */
	Trie() {//初始化函数
		root = new TreeNode(false);//将"皇帝"节点建出来
	}

	/** Inserts a word into the trie. */
	void insert(string word) {
		if (word.empty()) {//增加健壮性，空字符不存入
			return;
		}
		TreeNode* current = root;
		for (int i = 0; i < word.size(); i++) {
			int size = word[i] - 'a';//计算该字母应该映射到那个位置
			if (current->son[size] == nullptr) {//这是个没被访问过节点，那么先建立新节点再连上
				TreeNode* temp = new TreeNode(false);
				current->son[size] = temp;//与父结点相应映射位置相连
				current = temp;
			}
			else {//一旦这个节点之前已经被访问过了，那么不建立新节点了直接向下走
				current = current->son[size];
			}
		}
		current->is_end = true;//标志好这是最后一个节点
	}

	/** Returns if the word is in the trie. */
	bool search(string word) {//查找函数，所查的单词必须完整的在字典树里面，
		TreeNode* current = root;//即最后一个单词处在树里面截止标识符is_end必为true
		for (int i = 0; i < word.size(); i++) {
			int size = word[i] - 'a';//寻找该字母映射位置
			if (current->son[size] == nullptr) {//一旦发现这个字母没出现过必为false
				return false;
			}
			current = current->son[size];
		}
		if (current->is_end == false) {//判定是否到了结尾
			return false;
		}
		return true;
	}

	/** Returns if there is any word in the trie that starts with the given prefix. */
	bool startsWith(string prefix) {//和上面函数一样的思路只是不用判断
		TreeNode* current = root;//是否是截止位置，因为这里看的是前缀在不在
		for (int i = 0; i < prefix.size(); i++) {
			int size = prefix[i] - 'a';
			if (current->son[size] == nullptr) {//唯一错误情况，就是目标字母不在树里面
				return false;
			}
			current = current->son[size];
		}
		return true;
	}
private:
	struct TreeNode {
		bool is_end;//截止判定符
		TreeNode* son[26];//26儿子
		TreeNode(bool is_end) {//初始化
			this->is_end = is_end;
			for (int i = 0; i < 26; i++) {
				son[i] = nullptr;
			}
		}
	};
	TreeNode *root;//一个trie对象就是一颗树，那棵树就是私有成员变量root所指向的，在初始化的时候把根节点建出来.
};

（所有代码均已在力扣上运行无误）

经测试，该代码运行情况是(经过多次测试所得最短时间)：

时间复杂度：初始化为 O(1)，其余操作为 O(|S|)，其中 |S|是每次插入或查询的字符串的长度。

SumUp

1、只要能理解字典树构造就行，这些操作就顺水推舟的写出来了。
2、写相应操作的时候，一定先拿样例对应着写，最后拿复杂的样例与之比对，看看正确性以及完整不完整，缺不缺东西。

这篇关于淼淼刷力扣的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！