[Swift]LeetCode211. 添加与搜索单词 - 数据结构设计 | Add and Search Word - Data structure design

概述Design a data structure that supports the following two operations: void addWord(word)bool search(word) search(word) can search a literal word or a regular expression string containing only letter

Design a data structure that supports the following two operations:

voID adDWord(word)bool search(word)

search(word) can search a literal word or a regular Expression string containing only letters a-z or .. A . means it can represent any one letter.

Example:

adDWord("bad")adDWord("dad")adDWord("mad")search("pad") -> falsesearch("bad") -> truesearch(".ad") -> truesearch("b..") -> true

Note:
You may assume that all words are consist of lowercase letters a-z.

设计一个支持以下两种 *** 作的数据结构：

voID adDWord(word)bool search(word)

search(word) 可以搜索文字或正则表达式字符串，字符串只包含字母 . 或 a-z 。 . 可以表示任何一个字母。

示例:

adDWord("bad")adDWord("dad")adDWord("mad")search("pad") -> falsesearch("bad") -> truesearch(".ad") -> truesearch("b..") -> true

说明:

你可以假设所有单词都是由小写字母 a-z 组成的。

612ms

 1 class TrIENode { 2     var children: [Character: TrIENode] 3     var isEnd: Bool 4      5     init() { 6         children = [:] 7         isEnd = false 8     } 9 }10 11 class WordDictionary {12     13     private var root: TrIENode14     @H_419_113@/*@H_419_113@* Initialize your data structure here. @H_419_113@*/15     init() {16         root = TrIENode()17     }18     19     @H_419_113@/*@H_419_113@* Adds a word into the data structure. @H_419_113@*/20     func adDWord(_ word: String) {21         var node = self.root22         23         for c in Array(word) {24             if let next = node.children[c] {25                 node = next26             } else {27                 let newNode = TrIENode()28                 node.children[c] = newNode29                 node = newNode30             }31         }32         node.isEnd = true33     }34     35     @H_419_113@/*@H_419_113@* Returns if the word is in the data structure. A word Could contain the dot character ‘.‘ to represent any one letter. @H_419_113@*/36     func search(_ word: String) -> Bool {37         return self.match(Array(word),0,self.root)38     }39     40     private func match(_ chars: [Character],_ i :Int,_ node: TrIENode) -> Bool {41         @H_419_113@//@H_419_113@ if we reached the end42         if i == chars.count {43             return node.isEnd44         }45         let c = chars[i]46         if c != "." {47             guard let next = node.children[c] else { return false }48             return self.match(chars,i + 1,next)49         } else {50             for next in node.children.values {51                 if self.match(chars,next) {52                     return true53                 }54             }55         }56         57         return false58     }59 }60 61 @H_419_113@/*@H_419_113@*62 @H_419_113@ * Your WordDictionary object will be instantiated and called as such:63 @H_419_113@ * let obj = WordDictionary()64 @H_419_113@ * obj.adDWord(word)65 @H_419_113@ * let ret_2: Bool = obj.search(word)66  @H_419_113@*/

620ms

 1 class WordDictionary { 2     var trIE = TrIE() 3  4     @H_419_113@/*@H_419_113@* Initialize your data structure here. @H_419_113@*/ 5     init() { 6  7     } 8      9     @H_419_113@/*@H_419_113@* Adds a word into the data structure. @H_419_113@*/10     func adDWord(_ word: String) {11       trIE.add(word: word)12     }13     14     @H_419_113@/*@H_419_113@* Returns if the word is in the data structure. A word Could contain the dot character ‘.‘ to represent any one letter. @H_419_113@*/15     func search(_ word: String) -> Bool {16       return trIE.search(word:word)17     }18 }19 20 class TrIENode {21   var children: [Character: TrIENode]22   var isEnd: Bool23 24   init() {25     self.children = [Character: TrIENode]()26     self.isEnd = false27   }28 }29 30 31 class TrIE {32   var root: TrIENode33 34   init() {35     root = TrIENode()36   }37 38   func add(word: String) {39     var node = root40 41     for char in word {42       if node.children[char] == nil {43         node.children[char] = TrIENode()44       }45 46       node = node.children[char]!47     }48 49     node.isEnd = true50   }51   52   func search(word:String) -> Bool {53     return dfsSearch(word: word,index: 0,node: root)54   }55   56   fileprivate func dfsSearch(word: String,index: Int,node: TrIENode) -> Bool {57     if index == word.count {58       return node.isEnd59     }60     61     let char = Array(word)[index]62     63     if char != "." {64       guard let nextNode = node.children[char] else {65         return false66       }67       68       return dfsSearch(word: word,index: index + 1,node: nextNode)69     } else{70       for key in node.children.keys {71         if dfsSearch(word: word,index: index + 1,node: node.children[key]!) {72           return true73         }74       }75       76       return false77     }78   }79 }80 @H_419_113@/*@H_419_113@*81 @H_419_113@ * Your WordDictionary object will be instantiated and called as such:82 @H_419_113@ * let obj = WordDictionary()83 @H_419_113@ * obj.adDWord(word)84 @H_419_113@ * let ret_2: Bool = obj.search(word)85  @H_419_113@*/86  

644ms

  1 class TrIENode {  2     var children = [Character : TrIENode]()  3     var isEnd = false  4 }  5   6   7 class TrIE {  8     private let root: TrIENode  9      10     @H_419_113@/*@H_419_113@* Initialize your data structure here. @H_419_113@*/ 11     init() { 12         root = TrIENode() 13     } 14      15     @H_419_113@/*@H_419_113@* Inserts a word into the trIE. @H_419_113@*/ 16     func insert(_ word: String) { 17         var currentNode: TrIENode? = root 18         for c in word { 19             if let nextNode = currentNode?.children[c] { 20                 currentNode = nextNode 21             } else { 22                 let newNode = TrIENode() 23                  24                 currentNode?.children[c] = newNode 25                 currentNode = newNode 26             } 27         } 28          29         currentNode?.isEnd = true 30     } 31      32     @H_419_113@/*@H_419_113@* Returns if the word is in the trIE. @H_419_113@*/ 33     func search(_ word: String) -> Bool { 34         return searchNode(root,word: word,index: word.startIndex) 35     } 36      37     func searchNode(_ node: TrIENode,word: String,index: String.Index) -> Bool { 38         if index == word.endindex { 39             return node.isEnd 40         } 41          42         var currentNode: TrIENode? = root 43         let char = word[index] 44         if char == "." { 45             for (_,n) in node.children { 46                 if searchNode(n,index: word.index(after: index)) { 47                     return true 48                 } 49             } 50              51             return false 52         } else { 53             guard let nextNode = node.children[char] else { 54                 return false 55             } 56  57             return searchNode(nextNode,index: word.index(after: index)) 58         } 59     } 60      61     @H_419_113@/*@H_419_113@* Returns if there is any word in the trIE that starts with the given prefix. @H_419_113@*/ 62     func startsWith(_ prefix: String) -> Bool { 63       var currentNode: TrIENode? = root 64         for c in prefix { 65             guard let nextNode = currentNode?.children[c] else { 66                 return false 67             } 68              69             currentNode = nextNode 70         } 71          72         return true 73     } 74 } 75  76  77 class WordDictionary { 78     private let trIE = TrIE() 79      80      81     @H_419_113@/*@H_419_113@* Initialize your data structure here. @H_419_113@*/ 82     init() { 83          84     } 85      86     @H_419_113@/*@H_419_113@* Adds a word into the data structure. @H_419_113@*/ 87     func adDWord(_ word: String) { 88         trIE.insert(word) 89     } 90      91     @H_419_113@/*@H_419_113@* Returns if the word is in the data structure. A word Could contain the dot character ‘.‘ to represent any one letter. @H_419_113@*/ 92     func search(_ word: String) -> Bool { 93         return trIE.search(word) 94     } 95 } 96  97 @H_419_113@/*@H_419_113@* 98 @H_419_113@ * Your WordDictionary object will be instantiated and called as such: 99 @H_419_113@ * let obj = WordDictionary()100 @H_419_113@ * obj.adDWord(word)101 @H_419_113@ * let ret_2: Bool = obj.search(word)102  @H_419_113@*/103  

756ms

 1 class WordDictionary { 2     var trIE = TrIE() 3     @H_419_113@/*@H_419_113@* Initialize your data structure here. @H_419_113@*/ 4     init() { 5          6     } 7      8     @H_419_113@/*@H_419_113@* Adds a word into the data structure. @H_419_113@*/ 9     func adDWord(_ word: String) {10         trIE.insert(word)11     }12     13     @H_419_113@/*@H_419_113@* Returns if the word is in the data structure. A word Could contain the dot character ‘.‘ to represent any one letter. @H_419_113@*/14     func search(_ word: String) -> Bool {15         return trIE.search(word,trIE.root)16     }17 }18 19 class TrIENode {20     var isWord = false21     var next = [Character: TrIENode]()22     init(_ b: Bool = false) {23         isWord = b24     }25 }26 27 class TrIE {28     var root = TrIENode()29     func insert(_ word: String) {30         var cur = root31         for c in word {32             if cur.next[c] == nil {33                 cur.next[c] = TrIENode()34             }35             cur = cur.next[c]!36         }37         cur.isWord = true38     }39     40     func search(_ word: String,_ IDx: Int,_ node: TrIENode) -> Bool {41         var cur = node42         var chars = Array(word)43         for i in IDx..<chars.count {44             if let n = cur.next[chars[i]] {45                 cur = n46             } else if chars[i] != "." {47                 return false48             } else {49                 for n in cur.next.values {50                     if search(word,i+1,n) {51                         return true52                     }53                 }54                 return false55             }56         }57         return cur.isWord58     }59 }60 61 @H_419_113@/*@H_419_113@*62 @H_419_113@ * Your WordDictionary object will be instantiated and called as such:63 @H_419_113@ * let obj = WordDictionary()64 @H_419_113@ * obj.adDWord(word)65 @H_419_113@ * let ret_2: Bool = obj.search(word)66  @H_419_113@*/67  

764ms

 1 class TrIE { 2     var char: Character 3     var children: [Character :TrIE] 4      5     init(_ char: Character) { 6         self.char = char 7         self.children = [:] 8     } 9 }10 11 class WordDictionary {12     var root: TrIE13     @H_419_113@/*@H_419_113@* Initialize your data structure here. @H_419_113@*/14     init() {15         self.root = TrIE(Character(".")) 16     }17     18     @H_419_113@/*@H_419_113@* Adds a word into the data structure. @H_419_113@*/19     func adDWord(_ word: String) {20         var temp = root21         for char in word {22             if let child = temp.children[char] {23                 temp = child24             } else {25                 let newNode = TrIE(char)26                 temp.children[char] = newNode27                 temp = newNode28             }29         }30         let newNode = TrIE("$")31         temp.children["$"] = newNode32         temp = newNode33     }34     35     @H_419_113@/*@H_419_113@* Returns if the word is in the data structure. A word Could contain the dot character ‘.‘ to represent any one letter. @H_419_113@*/36     func search(_ word: String) -> Bool {37         return searchInternal(word,self.root)38     }39     40     private func searchInternal(_ word: String,_ node:TrIE) -> Bool {41         @H_419_113@//@H_419_113@ print("Searching word : \(word)")42         if word.isEmpty {43             @H_419_113@//@H_419_113@ print("ValID!!!!!!")44             if let child = node.children["$"] {45                 return true46             } else {47                 return false48             }49         }50         let firstChar = word[word.index(word.startIndex,offsetBy: 0)]51         let trimmeDWord = String(word[word.index(word.startIndex,offsetBy: 1)..<word.endindex])52         if firstChar == "." {53             for child in node.children {54                 let isValIDNode = self.searchInternal(trimmeDWord,child.value)55                 if isValIDNode {56                     return true57                     break58                 }59             }60         } else {61             if let child = node.children[firstChar] {62                 return self.searchInternal(trimmeDWord,child)63             } else {64                 @H_419_113@//@H_419_113@ print("not valID1")65                 return false66             }67         }68         @H_419_113@//@H_419_113@ print("not valID0")69         return false70     }71 }72 73 @H_419_113@/*@H_419_113@*74 @H_419_113@ * Your WordDictionary object will be instantiated and called as such:75 @H_419_113@ * let obj = WordDictionary()76 @H_419_113@ * obj.adDWord(word)77 @H_419_113@ * let ret_2: Bool = obj.search(word)78  @H_419_113@*/79  

总结

以上是内存溢出为你收集整理的[Swift]LeetCode211. 添加与搜索单词 - 数据结构设计 | Add and Search Word - Data structure design全部内容，希望文章能够帮你解决[Swift]LeetCode211. 添加与搜索单词 - 数据结构设计 | Add and Search Word - Data structure design所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。