Understanding Trie Data Structures with Swift

let searchKey = keyword.substring(to: current.level + 1) //iterate through child nodes for child in current.children { if child.key == searchKey { childToUse = child break } } //new node if childToUse == nil { childToUse = TrieNode() childToUse.key = searchKey childToUse.level = current.level + 1 current.children.append(childToUse) } current = childToUse } //end while //final end of word check if keyword.length == current.level { current.isFinal = true print("end of word reached!") return } } //end functionA final check confirms our keyword after completing the while loop..As part of this final check, we update the current node with the isFinal indicator..As mentioned, this step will allow us to distinguish words from phrases.FINDING WORDSThe algorithm for finding words is similar to adding content..Again, we establish a while loop to navigate the trie hierarchy..Since the goal will be to return a list of possible words, these will be tracked using an Array://find words based on the prefix func find(_ keyword: String) -> Array<String>?.{ //trivial case guard keyword.length > 0 else { return nil } var current: TrieNode = root var wordList = Array<String>() while keyword.length != current.level { var childToUse: TrieNode!.let searchKey = keyword.substring(to: current.level + 1) //iterate through any child nodes for child in current.children { if (child.key == searchKey) { childToUse = child current = childToUse break } } if childToUse == nil { return nil } } //end while //retrieve the keyword and any descendants if ((current.key == keyword) && (current.isFinal)) { if let key = current.key { wordList.append(key) } } //include only children that are words for child in current.children { if (child.isFinal == true) { if let key = child.key { wordList.append(key) } } } return wordList } //end functionThe search function checks to ensure keyword phrase permutations are found..Once the entire keyword is identified, we start the process of building our word list..In addition to returning keys identified as words (e.g., “Bat”, “Ball”), we account for the possibility of returning nil by returning an optional.EXTENDING SWIFTEven though we’ve written our trie in Swift, we’ve extended some language features to make things work..Previously known as categories in Objective-C, our algorithms employ two additional Swift extensions..The following class extends the functionality of the native String class:extension String { //compute the length var length: Int { return self.count } //returns characters up to a specified integer func substring(to: Int) -> String { //define the range let range = self.index(self.startIndex, offsetBy: to) return String(self[..<range]) } }. More details

Leave a Reply