算法模版 – 前缀树

前缀树需要实现3个函数：

• insert：往前缀树中插入单词
• search：查找前缀树中是否存在XX单词
• startwith：查找前缀树中是否存在XX前缀。

前缀树的数据结构为26叉树，该数据结构TrieNode如下：

• bool isWord;
• TrieNode* children[26]; (初始化为nullptr)

如果插入字符，则对应的char位置的指针从nullptr变成实际的TrieNode*。

insert函数步骤：

• 1 遍历输入字符串的每一个字符，进入root的children数组查找是否为nullptr，如果否则创建一个TrieNode。
• 2 设置字符串遍历结束后的TrieNode节点的isWord为True。

search函数步骤：

• 1 遍历输入字符串的每一个字符，进入root的children数组查找是否为nullptr，如果是，直接返回false,如果否，则继续遍历。
• 2 查看字符串遍历结束后的TrieNode节点的isWord是否为True。

startWith函数步骤：

• 1 遍历输入字符串的每一个字符，进入root的children数组查找是否为nullptr，如果是，直接返回false,如果否，则继续遍历。
• 2 能到字符串遍历结束后的节点，则返回true。

class TrieNode {
	public:
		bool isWord;
		TrieNode *children[26];
		TrieNode() {
			isWord = false;
			memset(children, 0, sizeof(children));
		}
};

class Trie {
	public:
		TrieNode *root;
		Trie() {
			root = new TrieNode();
		}

		bool insert(const string &word) {
			TrieNode *cur = root;
			for (int i = 0; i < word.size(); i++) { int c = word[i] - 'a'; if (cur->children[c] == nullptr) {
					cur->children[c] = new TrieNode();
				}
				cur = cur->children[c];
			}
			cur->isWord = true;
		}

		bool search(const string &word) {
			TrieNode *cur = root;
			for (int i = 0; i < word.size(); i++) { int c = word[i] - 'a'; if (cur->children[c] == nullptr) {
					return false;
				}
				cur = cur->children[c];
			}
			return cur->isWord;
		}

		bool startWith(const string &word) {
			TrieNode *cur = root;
			for (int i = 0; i < word.size(); i++) { int c = word[i] - 'a'; if (cur->children[c] == nullptr) {
					return false;
				}
				cur = cur->children[c];
			}
			return true;
		}
};