Learn how to implement the trie data structure in Swift - a data structure that is extremely handy for prefix-matching in the English language.
There is a bug in your code for removing a word. You can reproduce the bug with the following code:
trie.insert(word: “cute”)
trie.insert(word: “cut”)
trie.remove(word: “cute”)
trie.contains(word: “cut”)
trie.contains(word: “cute”)
The last statement returns false which is wrong.
To fix the bug, replace the code marked “4” with
if currentNode.children.count > 0 {
currentNode.isTerminating = false
} else {
var character = currentNode.value
while currentNode.children.count == 0, let parent = currentNode.parent {
currentNode = parent
currentNode.children[character!] = nil
character = currentNode.value
if currentNode.isTerminating {
break
}
}
}
Sorry, the last statement returns true.
Good catch @zampano! I’ll update the repository to correct that.
@Zampano Here’s the PR Fixes removal method bug for Trie by kelvinlauKL · Pull Request #310 · raywenderlich/swift-algorithm-club · GitHub. Feel free to give me some feedback so we can get some peer review going!
The insert method ends with the following two lines:
if currentIndex == characters.count {
currentNode.isTerminating = true
}
It seems that because of the condition on the while loop, this if will always be true and that the assignment alone is sufficient to complete this method. Are there any instances where this test makes a difference?
You mention that count, words and isEmpty are O(1) operations. isEmpty is fairly obvious. It seems that count would be O(1) if you introduce a new property count that gets increased every time isTerminating gets set to true and decreased every time it gets set to false. A count would then return the value of this property. Is there a better way to do this?
The words method would return a list of all of the words in the trie. I don’t see how this could be an O(1) operation. Wouldn’t it be a recursive traversal?
Even though the if statement confirms that
currentNode.children.count == 0
is true, don’t you still need the test in the while loop? You want to continue moving up removing all nodes that have zero children.
Peer review FTW 
Let’s bring this conversation over to the repo, so it’s easier to keep track of the discussions regarding the changes: Fixes removal method bug for Trie by kelvinlauKL · Pull Request #310 · raywenderlich/swift-algorithm-club · GitHub
I would like to see code for serializing a trie using NSCoding and saving it to a file. I’ve looked around for examples that use NSCoding to serialize a recursive structure, but haven’t found any. Does anyone have ideas on how to do this? The only downside of adding this (that I can see) is that the trie nodes can no longer be generic. A class that implements NSCoding cannot be generic. This doesn’t seem like a big problem to me though. The Trie class is based on the fact that nodes contain characters.
Hmm, I’m not sure. I suppose you want to avoid reconstructing the tree during deserialization? One way could be extracting all the words of the Trie, serializing that into an array. When you deserialize, you can reassemble it into a Trie.
We should get more eyes on this question by posting it on the repo. Interesting question
Loved the guide!
I was trying to create a recursive function that could search the Trie for words contained in an anagram. For example, it might take a scrambled string “rehnla” and would return and array of strings [“learn”,“heal”,“hen”, etc.]. The idea was described here Algorithm to get a list of all words that are anagrams of all substrings (scrabble)? - Stack Overflow
Any ideas on how I could try and implement this?
This tutorial is more than six months old so questions are no longer supported at the moment for it. We will update it as soon as possible. Thank you! :]