class TrieNode : CustomStringConvertible {
var description: String {
return children.keys.description + children.values.description
}
var children = [Character:TrieNode]()
var isFinal : Bool = false
func createOrReturn(_ char: Character) -> TrieNode{
if let child = children[char] {
return child
}
// create a new node
let newNode = TrieNode()
children[char] = newNode
return newNode
}
}
class Trie : CustomStringConvertible {
var description: String {return root.description }
var root = TrieNode()
// contains O(n)
func insert(_ inp: String) {
var node = root
for char in inp {
node = node.createOrReturn(char)
}
node.isFinal = true
}
// contains O(n)
func contains (word: String) -> Bool {
var node = root
for char in word {
if node.children[char] == nil {
return false
}
node = node.children[char]!
}
return node.isFinal
}
// removing just changes the isFinal boolean. It does not actually remove the elements
// from the trie
func remove (word: String) {
var node = root
for char in word {
if node.children[char] == nil {
return
}
node = node.children[char]!
}
node.isFinal = false
}
func getNodesList(word: String) -> [TrieNode]? {
var nodes : [TrieNode] = [root]
var node = root
for char in word {
if node.children[char] == nil {
return nil
}
node = node.children[char]!
nodes.append(node)
}
return nodes
}
// return a path for a given node. Returns true if done, false if failed.
func delete(word: String) -> Bool {
var nodes = getNodesList(word: word)
if nodes == nil {return false}
if !nodes!.last!.isFinal {return false}
for node in nodes!.reversed().enumerated() {
print ("node", node)
if (node.element.children.count == 0) {
}
return false
}
}
var myTrie = Trie()
trie
Be the first to comment
You can use [html][/html], [css][/css], [php][/php] and more to embed the code. Urls are automatically hyperlinked. Line breaks and paragraphs are automatically generated.