偷偷摘套内射激情视频,久久精品99国产国产精,中文字幕无线乱码人妻,中文在线中文a,性爽19p

一篇學好如何實現(xiàn) Trie

開發(fā) 前端
Trie又稱為字典樹,主要用于單詞的查找得名。如將一個單詞 Hello存放在字典樹中的數(shù)據(jù)結(jié)構(gòu)。

[[403657]]

本文轉(zhuǎn)載自微信公眾號「我好困啊」,作者mengxin。轉(zhuǎn)載本文請聯(lián)系我好困啊公眾號。

Trie又稱為字典樹,主要用于單詞的查找得名。如將一個單詞 Hello存放在字典樹中的數(shù)據(jù)結(jié)構(gòu)為:

當再次加入help時,此時的字典樹為:

當添加hero時,此時的字典樹為:

可以看到樹以每個單詞的字符為一個節(jié)點,直到字符添加完畢后設置上flag,標記當前節(jié)點結(jié)束為一個單詞(即從根節(jié)點到當前節(jié)點為一個單詞)。

當有新的單詞進來時,只需要添加到樹中即可,查找時,從根節(jié)點出發(fā),遍歷整棵樹(其實總是遍歷樹的某個分支)。如果其中一個字符不在樹中,則說明查找失敗,否則所有的word按每個字符的順序都能查找到,最后判斷結(jié)束節(jié)點是否為一個單詞,是,則查找成功。

代碼實現(xiàn)

  1. //葉子節(jié)點 
  2. type Node struct { 
  3.     isWord bool   //是否為一個單詞 
  4.     next map[uint8]*Node //葉子節(jié)點對應的單個字符及其next指針 
  5.  
  6. type Trie struct { 
  7.     root *Node 
  8.     size int64 
  9.  
  10. func Constructor() Trie { 
  11.     return Trie{&Node{ 
  12.         isWord: false
  13.         next:  make(map[uint8]*Node), 
  14.     },0} 
  15.  
  16. /** 添加單詞到字典中 */ 
  17. func (this *Trie) Insert(word string)  { 
  18.     if  word ==""
  19.         return 
  20.     } 
  21.     cur := this.root 
  22.  
  23.     for i:= 0;i< len(word);i++ { 
  24.         r := word[i] 
  25.         if  cur.next[r]== nil{ 
  26.             cur.next[r] = &Node{false, make(map[uint8]*Node)} 
  27.         } 
  28.         cur = cur.next[r] 
  29.     } 
  30.     if !cur.isWord { 
  31.         cur.isWord = true 
  32.     } 
  33.  
  34.  
  35.  
  36. /** 查找單詞 */ 
  37. func (this *Trie) Search(word string) bool { 
  38.     if  word ==""
  39.         return false 
  40.     } 
  41.     cur := this.root 
  42.  
  43.     for i:= 0;i< len(word);i++ { 
  44.         r := word[i] 
  45.         if  cur.next[r]== nil{ 
  46.             return false 
  47.         } 
  48.         cur = cur.next[r] 
  49.     } 
  50.     return cur.isWord 
  51.  
  52.  
  53. /**查找對應前綴 */ 
  54. func (this *Trie) StartsWith(prefix string) bool { 
  55.     if  prefix ==""
  56.         return false 
  57.     } 
  58.     cur := this.root 
  59.  
  60.     for i:= 0;i< len(prefix);i++ { 
  61.         r := prefix[i] 
  62.         if  cur.next[r]== nil{ 
  63.             return false 
  64.         } 
  65.         cur = cur.next[r] 
  66.     } 
  67.     return true 

 

 

責任編輯:武曉燕 來源: 我好困啊
相關推薦

2022-02-18 00:13:53

JavaScript編程語言數(shù)組

2021-04-08 11:00:56

CountDownLaJava進階開發(fā)

2022-04-08 08:32:40

mobx狀態(tài)管理庫redux

2021-11-04 10:34:02

JavaScript繼承編程

2024-04-02 12:36:01

2022-05-17 08:02:55

GoTryLock模式

2021-12-04 22:05:02

Linux

2022-03-17 19:29:04

CSS切角自適應

2021-12-07 08:50:40

字母區(qū)間字符串

2021-05-14 16:34:12

Semaphore原理

2021-09-05 07:55:36

Lsm核心實現(xiàn)

2022-05-25 08:31:31

ArthasInstrument

2021-07-12 06:11:14

SkyWalking 儀表板UI篇

2014-07-30 14:25:41

SwiftiBeacon

2022-10-08 15:07:06

ChatOps運維

2021-08-23 06:25:57

CSS 技巧animation

2024-05-28 09:21:25

2022-12-19 08:14:30

注解開發(fā)配置

2022-10-26 07:39:36

MVCC數(shù)據(jù)庫RR

2022-01-02 08:43:46

Python
點贊
收藏

51CTO技術棧公眾號