745. Prefix and Suffix Search

Question

Design a special dictionary with some words that searchs the words in it by a prefix and a suffix.

Implement the WordFilter class:

• WordFilter(string[] words) Initializes the object with the words in the dictionary.
• f(string prefix, string suffix) Returns the index of the word in the dictionary, which has the prefix prefix and the suffix suffix. If there is more than one valid index, return the largest of them. If there is no such word in the dictionary, return -1.

Solution

改版的前缀树，用后缀+符号+前缀的形式记录字典树。

TrieNode

用参数id记录TrieNode经历过的最大下标。

27位TrieNode数组children[]记录子TrieNode。

初始化

将words[]中的每个字符串记录在TrieNode上，保存TrieNode的根节点root。
在遍历每个字符串时，需要将每个“后缀+符号+前缀”组成的新字符串记录在字典树中，并更新当前节点的id值。

将后缀部分添加完毕后，加入特殊符号。检查并创建当前节点的curr[26]位置。
然后继续将整个前缀字符串加入字典树，并更新当前节点的id值。

搜索

搜索时，先遍历后缀，查找字典树的路径是否存在，并更新当前节点的位置，如不存在则返回-1。
然后检查并跳过curr.children[26]的位置，如不存在则返回-1。
最后遍历前缀，更新节点位置，如果路径不存在则返回-1。

最后返回当前节点的id即可。

Code

class WordFilter {
    class TrieNode{
        int id;
        TrieNode[] children;
        public TrieNode(){
            children = new TrieNode[27];
            id = 0;
        }
    }
    
    TrieNode root;
    public WordFilter(String[] words) {
        root = new TrieNode();
    
        for(int k = 0; k < words.length; k++){
            String word = words[k];
            for(int i = 0; i < word.length(); i++){
                TrieNode curr = root;
                int j = i;
                while(j < word.length()){
                    int index = word.charAt(j) - 'a';
                    if(curr.children[index] == null) curr.children[index] = new TrieNode();
                    curr = curr.children[index];
                    curr.id = k;
                    j++;
                }
                if(curr.children[26] == null) curr.children[26] = new TrieNode();
                curr = curr.children[26];
                curr.id = k;
                for(char c : word.toCharArray()){
                    int index = c - 'a';
                    if(curr.children[index] == null) curr.children[index] = new TrieNode();
                    curr = curr.children[index];
                    curr.id = k;
                }
            }
        }
    }
    
    public int f(String prefix, String suffix) {
        TrieNode curr = root;
        for(char c : suffix.toCharArray()){
            int index = c - 'a';
            if(curr.children[index] == null) return -1;
            curr = curr.children[index];
        }
        
        if(curr.children[26] == null) return -1;
        curr = curr.children[26];
        
        for(char c : prefix.toCharArray()){
            int index = c - 'a';
            if(curr.children[index] == null) return -1;
            curr = curr.children[index];
        }
        return curr.id;
    }
}

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