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。

One 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 *