Implement a trie in Swift, fast af

A trie, also known as a prefix tree, is a tree-like data structure that is used to store a dynamic set of strings. It is an efficient method for storing and searching for strings, as it allows for quick insertion and retrieval of data. In this tutorial, we will learn how to implement a trie in Swift and understand how it works.

Step 1: Create the Trie Node Class

First, let’s create a TrieNode class that represents a node in the trie. Each node will have an array of children nodes and a boolean value to indicate if it is the end of a word.

class TrieNode {
  var children: [TrieNode]
  var isEnd: Bool

  init() {
    children = [TrieNode]()
    isEnd = false
  }
}

Step 2: Create the Trie Class

Next, let’s create the Trie class that will hold the root node of the trie. We will add functions for inserting and searching for words in the trie.

class Trie {
  var root: TrieNode

  init() {
    root = TrieNode()
  }

  func insert(word: String) {
    var current = root

    for c in word.characters {
      let index = c.asciiValue - "a".asciiValue
      if current.children[index] == nil {
        current.children[index] = TrieNode()
      }
      current = current.children[index]
    }

    current.isEnd = true
  }

  func search(word: String) -> Bool {
    var current = root

    for c in word.characters {
      let index = c.asciiValue - "a".asciiValue
      if current.children[index] == nil {
        return false
      }
      current = current.children[index]
    }

    return current.isEnd
  }
}

In the insert function, we loop through each character in the word and add a new node for each character if it does not already exist. We mark the last node as the end of a word. In the search function, we do the same thing but return false if a node does not exist for a character.

Step 3: Test the Trie

Let’s test our trie by creating an instance and inserting some words.

let trie = Trie()
trie.insert(word: "apple")
trie.insert(word: "banana")
trie.insert(word: "cherry")

print(trie.search(word: "apple")) // true
print(trie.search(word: "banana")) // true
print(trie.search(word: "cherry")) // true
print(trie.search(word: "pear")) // false

Conclusion:

In this tutorial, we learned how to implement a trie in Swift and saw how it can be used to efficiently store and search for strings. Tries are useful in many applications such as spell checkers, autocomplete systems, and word games. I hope this tutorial has helped you understand how tries work and how to implement them in Swift.