struct Trie {
    class Node {
        var children = [Character: Node]()
        var isEOW = false // end of the word
    }

    let root: Node

    init() {
        root = Node()
    }

    func insert(_ word: String) {
        var node = root
        for ch in word {
            if node.children[ch] == nil {
                node.children[ch] = Node()
            }
            node = node.children[ch]!
        }
        node.isEOW = true
        assert(search(word), "\(node)")
    }

    func search(_ word: String) -> Bool {
        return findLastNode(word)?.isEOW ?? false
    }

    func startsWith(prefix: String) -> Bool {
        return findLastNode(prefix) != nil
    }

    private func findLastNode(_ word: String) -> Node? {
        var node = root
        for ch in word {
            if let n = node.children[ch] {
                node = n
            } else {
                return nil
            }
        }
        return node
    }
}