Find all keys in patricia trie that are prefix of a string

Question

I am trying to find all keys stored in a trie that are valid prefixes of a string.

Example: Given a trie that contains "ab", "abc", "abcd", "bc" and "bcd". Searching for the string "abcdefg" in the trie should yield "abcd", "abc", "ab".

I would like to use the appache commons patricia trie implementation for java but it does not seem to support this kind of lookup. Is there any alternative implementation or simple solution to this problem?

Answer 1

I myself haven't used the Apache Commons PatriciaTrie, but as far as I checked you can easily get only the map of words prefixed with some string. Most of the examples I found are also providing basic operations like insert, find. I also encountered some discussions about a Trie implementation in guava, but nothing really specific.

So here is my simple suggestion of a custom implementation (but should be covered with a good set of tests when a custom implementation is used).

public class SimpleTrie {

    private static final int ALPHABET_COUNT = 26;

    class TrieNode {
        char value;
        TrieNode[] children;
        boolean isValidWord;

        TrieNode() {
            this(' ');
        }

        TrieNode(char value) {
            this.value = value;
            children = new TrieNode[ALPHABET_COUNT];
            isValidWord = false;
        }
    }

    private TrieNode root = new TrieNode();

    public void insert(String word) {
        TrieNode current = root;

        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);

            if (current.children[c - 'a'] == null) {
                current.children[c - 'a'] = new TrieNode(c);
            }

            current = current.children[c - 'a'];
        }

        current.isValidWord = true;
    }

    public List<String> findValidPrefixes(String word) {
        List<String> prefixes = new ArrayList<>();
        TrieNode current = root;

        StringBuilder traversedPrefix = new StringBuilder();

        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);

            if (current.children[c - 'a'] != null) {
                current = current.children[c - 'a'];
                traversedPrefix.append(c);

                if (current.isValidWord) {
                    prefixes.add(traversedPrefix.toString());
                }
            }
        }

        return prefixes;
    }

    public static void main(String[] args) {
       SimpleTrie trie = new SimpleTrie();

        // insert "ab", "abc", "abcd", "bc" and "bcd"
        trie.insert("ab");
        trie.insert("abc");
        trie.insert("abcd");
        trie.insert("bc");
        trie.insert("bcd");

        List<String> validPrefixes = trie.findValidPrefixes("abcdefg");

        System.out.println(validPrefixes);
    }
}