class TrieNode(object):
def __init__(self):
"""
Initialize your data structure here.
"""
self.isString=False
self.leaves={}
class Trie(object):
def __init__(self):
self.root = TrieNode()
def insert(self, word):
"""
Inserts a word into the trie.
:type word: str
:rtype: void
"""
cur=self.root
for c in word:
if c not in cur.leaves:
cur.leaves[c]=TrieNode()
cur=cur.leaves[c]
cur.isString=True
def search(self, word):
"""
Returns if the word is in the trie.
:type word: str
:rtype: bool
"""
node=self.searchChild(word)
if node:
return node.isString
return False
def startsWith(self, prefix):
"""
Returns if there is any word in the trie
that starts with the given prefix.
:type prefix: str
:rtype: bool
"""
if self.searchChild(prefix): return True
return False
def searchChild(self,word):
cur=self.root
for c in word:
if c not in cur.leaves:
return None
else:
cur=cur.leaves[c]
return cur
# Your Trie object will be instantiated and called as such:
# trie = Trie()
# trie.insert("somestring")
# trie.search("key")
208. Implement Trie (Prefix Tree)
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
- 文/潘曉璐 我一進(jìn)店門(mén)，熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)洛波，“玉大人胰舆，你說(shuō)我怎么就攤上這事〉偶罚” “怎么了缚窿？”我有些...
- 文/不壞的土叔 我叫張陵，是天一觀的道長(zhǎng)焰扳。 經(jīng)常有香客問(wèn)我倦零，道長(zhǎng)，這世上最難降的妖魔是什么吨悍？ 我笑而不...
- 正文 為了忘掉前任扫茅，我火速辦了婚禮，結(jié)果婚禮上育瓜，老公的妹妹穿的比我還像新娘诞帐。我一直安慰自己，他們只是感情好爆雹，可當(dāng)我...
- 文/花漫 我一把揭開(kāi)白布。 她就那樣靜靜地躺著愕鼓，像睡著了一般钙态。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上菇晃，一...
- 那天册倒，我揣著相機(jī)與錄音，去河邊找鬼磺送。 笑死驻子，一個(gè)胖子當(dāng)著我的面吹牛灿意，可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播崇呵，決...
- 文/蒼蘭香墨 我猛地睜開(kāi)眼缤剧，長(zhǎng)吁一口氣：“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼！你這毒婦竟也來(lái)了域慷？” 一聲冷哼從身側(cè)響起荒辕，我...
- 序言：老撾萬(wàn)榮一對(duì)情侶失蹤，失蹤者是張志新（化名）和其女友劉穎犹褒，沒(méi)想到半個(gè)月后抵窒，有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體，經(jīng)...
- 正文 獨(dú)居荒郊野嶺守林人離奇死亡叠骑，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
- 正文 我和宋清朗相戀三年李皇，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片宙枷。...
- 正文 年R本政府宣布璧帝，位于F島的核電站捍岳，受9級(jí)特大地震影響，放射性物質(zhì)發(fā)生泄漏睬隶。R本人自食惡果不足惜锣夹，卻給世界環(huán)境...
- 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望苏潜。 院中可真熱鬧银萍，春花似錦、人聲如沸恤左。這莊子的主人今日做“春日...
- 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)飞袋。三九已至戳气，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間巧鸭，已是汗流浹背瓶您。 一陣腳步聲響...
- 正文 我出身青樓贸毕，卻偏偏與公主長(zhǎng)得像，于是被迫代替她去往敵國(guó)和親夜赵。 傳聞我的和親對(duì)象是個(gè)殘疾皇子明棍，可洞房花燭夜當(dāng)晚...
推薦閱讀更多精彩內(nèi)容
- 實(shí)現(xiàn)前綴樹(shù)。 這題畫(huà)個(gè)圖就容易懂油吭。但是在寫(xiě)````search 和startWith```的時(shí)候我發(fā)現(xiàn)自己還是不夠...
- 原題 實(shí)現(xiàn)一個(gè) Trie击蹲，包含 insert, search, 和 startsWith 這三個(gè)方法。 樣例 解題...
- Implement a trie with insert, search, and startsWith meth...
- Implement a trie with insert, search, and startsWith meth...
