745. Prefix and Suffix Search

• Leetcode - 745. Prefix and Suffix Search

Submission

class WordFilter {
    Trie trie;
    static class TrieNode {
        public Map<Character, TrieNode> children;
        public int index;

        public TrieNode() {
            this.children = new HashMap<>();
        }
    }

    static class Trie {
        public TrieNode root;

        public Trie() {
            this.root = new TrieNode();
        }

        public void insert(String s, int index) {
            TrieNode current = root;
            for (char l : s.toCharArray()) {
                current = current.children.computeIfAbsent(l, c -> new TrieNode());
                current.index = index;
            }
        }
    }

    public WordFilter(String[] words) {
        this.trie = new Trie();
        for (int i = 0; i < words.length; i++) {
            insert(words[i], i);
        }
    }

    public int f(String prefix, String suffix) {
        String s = suffix + "#" + prefix;
        TrieNode current = trie.root;
        for (char c : s.toCharArray()) {
            current = current.children.get(c);
            if (current == null) return -1;
        }

        return current.index;
    }

    private void insert(String word, int index) {
        char[] chars = word.toCharArray();
        this.trie.insert("#" + word, index);
        StringBuilder sb = new StringBuilder();
        for (int i = chars.length - 1; i >= 0; i--) {
            sb.insert(0, chars[i]);
            this.trie.insert(sb.toString() + "#" + word, index);
        }
    }
}

/**
 * Your WordFilter object will be instantiated and called as such:
 * WordFilter obj = new WordFilter(words);
 * int param_1 = obj.f(prefix,suffix);
 */