Trie

public struct Trie

A Trie (sometimes called a prefix tree) is used for storing a set of strings compactly and searching for full words or partial prefixes very efficiently.

The operations for insertion, removal, lookup, and prefix matching run in O(n) time, where n is the length of the sequence or prefix.

Conforms to CustomStringConvertible, Hashable.

Creating a Trie

  • Constructs an empty Trie.

    Declaration

    Swift

    public init()

  • Constructs a trie from a sequence, such as an array. Inserts all the elements from the given sequence into the trie.

    Declaration

    Swift

    public init<S: Sequence>(_ elements: S) where S.Iterator.Element == String

Querying a Trie

  • Number of words stored in the trie.

    Declaration

    Swift

    public fileprivate(set) var count = 0

  • Returns true if and only if count == 0.

    Declaration

    Swift

    public var isEmpty: Bool

  • Reconstructs and returns all the words stored in the trie.

    Declaration

    Swift

    public var elements: [String]

  • Returns true if the trie contains the given word and it’s not just a prefix of another word.

    Declaration

    Swift

    public func contains(_ word: String) -> Bool

  • Returns true if the trie contains at least one word matching the given prefix or if the given prefix is empty.

    Declaration

    Swift

    public func isPrefix(_ prefix: String) -> Bool

  • Returns all the words in the trie matching the given prefix.

    Declaration

    Swift

    public func findPrefix(_ prefix: String) -> [String]

  • Returns the longest prefix in the trie matching the given word. The returned value is not necessarily a full word in the trie.

    Declaration

    Swift

    public func longestPrefixIn(_ element: String) -> String

Adding and Removing Elements

  • Inserts the given word into the trie.

    Declaration

    Swift

    public mutating func insert(_ word: String) -> Bool

    Return Value

    true if the trie did not already contain the word.

  • Removes the given word from the trie and returns it if it was present. This does not affect other words matching the given word as a prefix.

    Declaration

    Swift

    public mutating func remove(_ word: String) -> String?

  • Removes all the words from the trie.

    Declaration

    Swift

    public mutating func removeAll()

CustomStringConvertible Protocol Conformance

  • A string containing a suitable textual representation of the trie.

    Declaration

    Swift

    public var description: String

CustomDebugStringConvertible Protocol Conformance

  • A string containing a suitable textual representation of the trie when debugging.

    Declaration

    Swift

    public var debugDescription: String

Hashable Protocol Conformance

  • The hash value. x == y implies x.hashValue == y.hashValue

    Declaration

    Swift

    public var hashValue: Int