題目描述

Implement a trie with?insert,?search, and?startsWith?methods.

?

題目大意

實現對一棵樹的插入、搜索以及前序查找操作。

（樹的每個節點代表一個小寫字母，從根節點到葉節點代表一個完整的單詞）

?

示例

E

Trie trie = new Trie();trie.insert("apple"); trie.search("apple"); // returns true trie.search("app"); // returns false trie.startsWith("app"); // returns true trie.insert("app"); trie.search("app"); // returns true

?

解題思路

感謝Leetcode@cxq1992提供的思路，采用較為工程化的方法完成樹結點的記錄保存與操作。

?

復雜度分析

時間復雜度：O(NULL)

空間復雜度：O(NULL)

?

代碼

class node { public:node() : val(' '), end(false), shared(0) {}node(char c) : val(c), end(false), shared(0) {}node* subchild(char c) {if(!child.empty()) {for(auto chi : child) {if(chi->val == c)return chi;}}return NULL;}~node() {for(auto chi : child)delete chi;}//該樹結點所保存的小寫字母char val;//該結點是否是葉節點bool end;//子節點的個數int shared;//子節點保存vector<node*> child; };class Trie { public:/** Initialize your data structure here. */Trie() {root = new node();}/** Inserts a word into the trie. */void insert(string word) {if(search(word))return;node* cur = root;for(char c : word) {node* tmp = cur->subchild(c);if(tmp == NULL) {tmp = new node(c);cur->child.push_back(tmp);cur = tmp;}else {cur = tmp;}++cur->shared;}cur->end = true;}/** Returns if the word is in the trie. */bool search(string word) {node* tmp = root;for(char c : word) {tmp = tmp->subchild(c);if(tmp == NULL)return false;}return tmp->end;}/** Returns if there is any word in the trie that starts with the given prefix. */bool startsWith(string prefix) {node* tmp = root;for(char c : prefix) {tmp = tmp->subchild(c);if(tmp == NULL)return false;}return true;}private:node* root; };/*** Your Trie object will be instantiated and called as such:* Trie* obj = new Trie();* obj->insert(word);* bool param_2 = obj->search(word);* bool param_3 = obj->startsWith(prefix);*/

?

轉載于:https://www.cnblogs.com/heyn1/p/11016344.html

總結

以上是生活随笔為你收集整理的LeetCode-208 Implement Trie (Prefix Tree)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。