Package edu.princeton.cs.algs4

Class TrieSET

  • All Implemented Interfaces:
    Iterable<String>
    public class TrieSET
extends Object
implements Iterable<String>
    The TrieSET class represents an ordered set of strings over the extended ASCII alphabet. It supports the usual add, contains, and delete methods. It also provides character-based methods for finding the string in the set that is the longest prefix of a given prefix, finding all strings in the set that start with a given prefix, and finding all strings in the set that match a given pattern.

    This implementation uses a 256-way trie. The add, contains, delete, and longest prefix methods take time proportional to the length of the key (in the worst case). Construction takes constant time.

    For additional documentation, see Section 5.2 of Algorithms in Java, 4th Edition by Robert Sedgewick and Kevin Wayne.

    Author:
    Robert Sedgewick, Kevin Wayne

    • Constructor Detail

      • TrieSET

        public TrieSET()
        Initializes an empty set of strings.

    • Method Detail

      • contains

        public boolean contains​(String key)
        Does the set contain the given key?
        Parameters:
        key - the key
        Returns:
        true if the set contains key and false otherwise
        Throws:
        IllegalArgumentException - if key is null

      • add

        public void add​(String key)
        Adds the key to the set if it is not already present.
        Parameters:
        key - the key to add
        Throws:
        IllegalArgumentException - if key is null

      • size

        public int size()
        Returns the number of strings in the set.
        Returns:
        the number of strings in the set

      • isEmpty

        public boolean isEmpty()
        Is the set empty?
        Returns:
        true if the set is empty, and false otherwise

      • iterator

        public Iterator<String> iterator()
        Returns all of the keys in the set, as an iterator. To iterate over all of the keys in a set named set, use the foreach notation: for (Key key : set).
        Specified by:
        iterator in interface Iterable<String>
        Returns:
        an iterator to all of the keys in the set

      • keysWithPrefix

        public Iterable<String> keysWithPrefix​(String prefix)
        Returns all of the keys in the set that start with prefix.
        Parameters:
        prefix - the prefix
        Returns:
        all of the keys in the set that start with prefix, as an iterable

      • keysThatMatch

        public Iterable<String> keysThatMatch​(String pattern)
        Returns all of the keys in the set that match pattern, where the character '.' is interpreted as a wildcard character.
        Parameters:
        pattern - the pattern
        Returns:
        all of the keys in the set that match pattern, as an iterable, where . is treated as a wildcard character.

      • longestPrefixOf

        public String longestPrefixOf​(String query)
        Returns the string in the set that is the longest prefix of query, or null, if no such string.
        Parameters:
        query - the query string
        Returns:
        the string in the set that is the longest prefix of query, or null if no such string
        Throws:
        IllegalArgumentException - if query is null

      • delete

        public void delete​(String key)
        Removes the key from the set if the key is present.
        Parameters:
        key - the key
        Throws:
        IllegalArgumentException - if key is null

      • main

        public static void main​(String[] args)
        Unit tests the TrieSET data type.
        Parameters:
        args - the command-line arguments