[Swift]LeetCode208. 实现 Trie (前缀树) | Implement Trie (Prefix Tree)

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/10187360.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

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

Example:

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

Note:

You may assume that all inputs are consist of lowercase letters a-z.
All inputs are guaranteed to be non-empty strings.

实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。

示例:

Trie trie = new Trie();

trie.insert("apple");
trie.search("apple");   // 返回 true
trie.search("app");     // 返回 false
trie.startsWith("app"); // 返回 true
trie.insert("app");   
trie.search("app");     // 返回 true

说明:

你可以假设所有的输入都是由小写字母 a-z 构成的。
保证所有输入均为非空字符串。

424ms

 1 class Node {
 2     var wordEnd = false
 3     var next : [Character : Node] = [:]
 4 }
 5 
 6 class Trie {
 7     let root = Node()
 8     /** Initialize your data structure here. */
 9     init() {
10         
11     }
12     
13     /** Inserts a word into the trie. */
14     func insert(_ word: String) {
15       var currentNode = root
16         for c in word {
17             if let nextNode = currentNode.next[c] {
18                 currentNode = nextNode
19             } else {
20                 let nextNode = Node()
21                 currentNode.next[c] = nextNode
22                 currentNode = nextNode
23             }
24         }
25         currentNode.wordEnd = true
26     }
27     
28     /** Returns if the word is in the trie. */
29     func search(_ word: String) -> Bool {
30       var currentNode = root
31       for c in word {
32           if let node = currentNode.next[c] {
33               currentNode = node
34           } else {
35               return false
36           }
37       }
38         return currentNode.wordEnd
39     }
40     
41     /** Returns if there is any word in the trie that starts with the given prefix. */
42     func startsWith(_ prefix: String) -> Bool {
43       var currentNode = root
44       for c in prefix {
45           if let node = currentNode.next[c] {
46               currentNode = node
47           } else {
48               return false
49           }
50       }
51         return true
52     }
53 }
54 
55 /**
56  * Your Trie object will be instantiated and called as such:
57  * let obj = Trie()
58  * obj.insert(word)
59  * let ret_2: Bool = obj.search(word)
60  * let ret_3: Bool = obj.startsWith(prefix)
61  */
62

432ms

 1 class Node {
 2     var ch: Character
 3     var children: [Node?]
 4     var isWord: Bool
 5     init () {
 6         self.ch = "*"
 7         self.children = Array(repeating: nil, count: 26)
 8         self.isWord = false
 9     }
10         
11     init (_ ch: Character) {
12         self.ch = ch
13         self.children = Array(repeating: nil, count: 26)
14         self.isWord = false
15     }
16 }
17 class Trie {
18 
19     private var root: Node
20     /** Initialize your data structure here. */
21     init() {
22         root = Node()
23     }
24     
25     /** Inserts a word into the trie. */
26     func insert(_ word: String) {
27         var cur = root
28           for c in word {
29               if let node = cur.children[c.toValue - 97] {
30                   cur = node
31               }
32               else {
33                   let node = Node(c)
34                   cur.children[c.toValue - 97] = node
35                   cur = node
36               }
37           }
38         cur.isWord = true
39         
40     }
41     
42     /** Returns if the word is in the trie. */
43     func search(_ word: String) -> Bool {
44         var cur = root
45           for c in word {
46               if let node = cur.children[c.toValue - 97] {
47                   cur = node
48               }
49               else {
50                   return false
51               }
52           }
53         return cur.isWord == true   
54     }
55     
56     /** Returns if there is any word in the trie that starts with the given prefix. */
57     func startsWith(_ prefix: String) -> Bool {
58               var cur = root
59           for c in prefix {
60               if let node = cur.children[c.toValue - 97] {
61                   cur = node
62               }
63               else {
64                   return false
65               }
66           }
67         return  true    
68     }
69 }
70 extension Character {
71     var toValue: Int {
72         let characterString = String(self)
73         let scalars = characterString.unicodeScalars
74 
75         return Int(scalars[scalars.startIndex].value)
76     }
77 }
78 /**
79  * Your Trie object will be instantiated and called as such:
80  * let obj = Trie()
81  * obj.insert(word)
82  * let ret_2: Bool = obj.search(word)
83  * let ret_3: Bool = obj.startsWith(prefix)
84  */
85

436ms

 1 class Trie {
 2 
 3     class TrieNode {
 4         let val: Character
 5         var childs = [Character: TrieNode]()
 6         
 7         init(_ val: Character) {
 8             self.val = val
 9         }
10     }
11     
12     let trie = TrieNode("0")
13     
14     /** Initialize your data structure here. */
15     init() {
16         
17     }
18     
19     /** Inserts a word into the trie. */
20     func insert(_ word: String) {
21         var current = trie
22         for c in word+"#" {
23             if let child = current.childs[c] {
24                 current = child
25             } else {
26                 let new = TrieNode(c)
27                 current.childs[c] = new
28                 current = new
29             }
30         }
31     }
32     
33     /** Returns if the word is in the trie. */
34     func search(_ word: String) -> Bool {
35         var current = trie
36         for c in word+"#" {
37             if let child = current.childs[c] {
38                 current = child
39             } else {
40                 return false
41             }
42         }
43       
44         return current.childs.isEmpty
45     }
46     
47     /** Returns if there is any word in the trie that starts with the given prefix. */
48     func startsWith(_ prefix: String) -> Bool {
49       var current = trie
50         for c in prefix {
51             if let child = current.childs[c] {
52                 current = child
53             } else {
54                 return false
55             }
56         }
57       
58         return true
59     }
60 }
61 
62 /**
63  * Your Trie object will be instantiated and called as such:
64  * let obj = Trie()
65  * obj.insert(word)
66  * let ret_2: Bool = obj.search(word)
67  * let ret_3: Bool = obj.startsWith(prefix)
68  */
69

452ms

 1 class TrieNode
 2 {
 3     var child:[TrieNode?]
 4     var isWord:Bool = false
 5     init()
 6     {
 7         child = [TrieNode?](repeating:nil,count:26)
 8     }
 9 }
10 
11 
12 class Trie {
13     var root:TrieNode?
14 
15     /** Initialize your data structure here. */
16     init() {
17         root = TrieNode()
18     }
19     
20     /** Inserts a word into the trie. */
21     func insert(_ word: String) {
22         var p:TrieNode? = root
23         for a in word.characters
24         {
25             var i:Int = a.ascii - 97
26             if p!.child[i] == nil
27             {
28                 p!.child[i] = TrieNode()
29             }
30             p = p!.child[i]
31         }
32         p!.isWord = true
33     }
34     
35     /** Returns if the word is in the trie. */
36     func search(_ word: String) -> Bool {
37         var p:TrieNode? = root
38         for a in word.characters
39         {
40             var i:Int = a.ascii - 97
41             if p?.child[i] == nil
42             {
43                return false
44             }
45             p = p!.child[i]
46         }
47         return p!.isWord
48     }
49     
50     /** Returns if there is any word in the trie that starts with the given prefix. */
51     func startsWith(_ prefix: String) -> Bool {
52         var p:TrieNode? = root
53         for a in prefix.characters
54         {
55             var i:Int = a.ascii - 97
56             if p?.child[i] == nil
57             {
58                return false
59             }
60             p = p!.child[i]
61         }
62         return true
63     }
64 }
65 
66 //Character扩展方法  
67 extension Character  
68 {  
69   //属性：ASCII整数值(定义小写为整数值)
70    var ascii: Int {
71         get {
72             let s = String(self).unicodeScalars
73             return Int(s[s.startIndex].value)
74         }
75     }
76 }
77 /**
78  * Your Trie object will be instantiated and called as such:
79  * let obj = Trie()
80  * obj.insert(word)
81  * let ret_2: Bool = obj.search(word)
82  * let ret_3: Bool = obj.startsWith(prefix)
83  */
84

460ms

 1 class Trie {
 2     /** Initialize your data structure here. */
 3     init() {
 4         
 5     }
 6     
 7     /** Inserts a word into the trie. */
 8     func insert(_ word: String) {
 9         var root = self.root
10         
11         let unicodeScalars = Array(word.utf8)
12         
13         for character in unicodeScalars {
14             let ascii = Int(character - 97)
15             
16             if root.children[ascii] == nil {
17                 
18                 root.children[ascii] = TrieNode(String(character))
19             }
20             
21             root = root.children[ascii]!
22         }
23         root.isEnd = true
24     }
25     
26     /** Returns if the word is in the trie. */
27     func search(_ word: String) -> Bool {
28         var root = self.root
29         
30         let unicodeScalars = Array(word.utf8)
31         
32         for character in unicodeScalars {
33             let ascii = Int(character - 97)
34             
35             guard let node = root.children[ascii] else {
36                 return false
37             }
38             root = node
39         }
40         
41         return root.isEnd
42     }
43     
44     /** Returns if there is any word in the trie that starts with the given prefix. */
45     func startsWith(_ prefix: String) -> Bool {
46         var root = self.root
47         
48         let unicodeScalars = Array(prefix.utf8)
49         
50         for character in unicodeScalars {
51             let ascii = Int(character - 97)
52             
53             guard let node = root.children[ascii] else {
54                 return false
55             }
56             root = node
57         }
58         
59         return true
60     }
61     
62     var root = TrieNode("")
63     
64 }
65 
66 class TrieNode {
67     
68     init(_ value: String) {
69         self.value = value
70     }
71     
72     var value : String
73     
74     
75     var isEnd = false
76     
77     var children : [TrieNode?] = Array(repeating: nil, count: 26)
78     
79 }
80 
81 /**
82  * Your Trie object will be instantiated and called as such:
83  * let obj = Trie()
84  * obj.insert(word)
85  * let ret_2: Bool = obj.search(word)
86  * let ret_3: Bool = obj.startsWith(prefix)
87  */
88