LeetCode Implement Trie (Prefix Tree)

LeetCode Implement Trie (Prefix Tree)
Implement a trie with insert, search, and startsWith methods.
Note:
You may assume that all inputs are consist of lowercase letters a-z.


本题要求实现只包含26个小写字母的trie树。因为之前做过hihoCoder 1014-Trie树,所以实现起来并不费劲。
定义一个Node结构体,包含三个成员,char c表示该Node的字符,bool isWord表示以该Node结尾是否能构成一个单词,children表示该Node的26个孩子。
初始化的时候就初始化一个根节点。
插入一个单词时,不断从根节点往下创建节点,到最后一个字符所在节点时,标记isWord为true。
搜索一个单词时,也是不断从根节点往下搜索,如果到单词尾所在的Node的isWord为true,说明找到该单词,否则要么到不了最后一个字符,要么到了最后一个字符,isWord为false,都表示搜索失败。
搜索是否有某个前缀的单词存在,和搜索一个单词几乎一样,只不过最后返回时,不需要判断isWord是否为true,只要能到达prefix的最后一个字符的Node,说明后面肯定有以该字符串为前缀的单词存在。
完整代码如下:

const int MAXN = 26;
class Trie {
private:
	struct Node
	{
		char c;
		bool isWord;
		Node(char c_, bool isWord_) :c(c_), isWord(isWord_) {
			for (int i = 0; i < MAXN; ++i)children.push_back(NULL);
		};
		vector<Node*> children;
	};
	Node *root;
public:
	/** Initialize your data structure here. */
	Trie() {
		root = new Node(' ', true);
	}
	/** Inserts a word into the trie. */
	void insert(string word) {
		Node *cur = root;
		for (int i = 0; i < word.size(); ++i) {
			int idx = word[i] - 'a';
			if (cur->children[idx] == NULL)cur->children[idx] = new Node(word[i], false);
			cur = cur->children[idx];
		}
		cur->isWord = true;
	}
	/** Returns if the word is in the trie. */
	bool search(string word) {
		Node *cur = root;
		for (int i = 0; i < word.size(); ++i) {
			int idx = word[i] - 'a';
			if (cur->children[idx] == NULL)return false;
			cur = cur->children[idx];
		}
		return cur->isWord;
	}
	/** Returns if there is any word in the trie that starts with the given prefix. */
	bool startsWith(string prefix) {
		Node *cur = root;
		for (int i = 0; i < prefix.size(); ++i) {
			int idx = prefix[i] - 'a';
			if (cur->children[idx] == NULL)return false;
			cur = cur->children[idx];
		}
		return true;
	}
};

本代码提交AC,用时118MS。

1 thought on “LeetCode Implement Trie (Prefix Tree)

  1. Pingback: LeetCode Add and Search Word – Data structure design | bitJoy > code

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.