745. Prefix and Suffix Search

Description

Design a special dictionary which has some words and allows you to search 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.

Constraints

1 <= words.length <= 15000
1 <= words[i].length <= 10
1 <= prefix.length, suffix.length <= 10
words[i], prefix and suffix consist of lower-case English letters only.
At most 15000 calls will be made to the function f.

Approach

Examples

Input:

["WordFilter", "f"]

[[["apple"]], ["a", "e"]]

Output:

[null, 0]

Explanation:

WordFilter wordFilter = new WordFilter(["apple"]);

wordFilter.f("a", "e"); // return 0, because the word at index 0 has prefix = "a" and suffix = 'e".

Solutions

/**
 * Time complexity : 
 * Space complexity : 
 */

class WordFilter {
    
    private Map<String, Integer> map;

    public WordFilter(String[] words) {
        map = new HashMap();
        
        for(int i = 0; i < words.length; i++) {
            String word = words[i];
            
            List<String> prefix = new ArrayList();
            List<String> suffix = new ArrayList();
            
            for(int j = 0; j <= word.length(); j++) {
                prefix.add(word.substring(0, j));
                suffix.add(word.substring(j));
            }
            
            for(String p: prefix) {
                for(String s: suffix) {
                    String key = p + "#" + s;
                    map.put(key, Math.max(map.getOrDefault(key, 0), i));
                }
            }
        }
    }
    
    public int f(String prefix, String suffix) {
        String word = prefix + "#" + suffix;
        return map.getOrDefault(word, -1);
    }
}

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

/**
 * Time complexity : 
 * Space complexity : 
 */
 
 class WordFilter {
    private Trie forward;
    private Trie backward;
    
    public WordFilter(String[] words) {
        forward = new Trie(true);
        backward = new Trie(false);
        
        for(int i = 0; i < words.length; i++) {
            forward.addWord(words[i], i);
            backward.addWord(words[i], i);
        }
    }
    
    public int f(String prefix, String suffix) {
        List<Integer> l1 = forward.startsWith(prefix);
        List<Integer> l2 = backward.startsWith(suffix);
        
        int i1 = l1.size() - 1;
        int i2 = l2.size() - 1;
        while(i1 >= 0 && i2 >= 0) {
            int a = l1.get(i1);
            int b = l2.get(i2);
            
            if(a > b) {
                i1--;
            } else if(a < b) {
                i2--;
            } else {
                return a;
            }
        }
        return -1;
    }
}

class Trie {
    TrieNode root;
    boolean forward;
    
    public Trie(boolean fwd) {
        root = new TrieNode();
        forward = fwd;
    }
    
    public void addWord(String word, int idx) {
        TrieNode cur = root;
        for(int i = 0; i < word.length(); i++) {
            char c = this.forward ? word.charAt(i): word.charAt(word.length()-i-1);
            if(cur.children[c - 'a'] == null) {
                cur.children[c - 'a'] = new TrieNode();
            }
            cur = cur.children[c - 'a'];
            cur.indices.add(idx);
        }
    }
    
    public List<Integer> startsWith(String word) {
        TrieNode cur = root;
        for(int i = 0; i < word.length(); i++) {
            char c = this.forward ? word.charAt(i): word.charAt(word.length()-i-1);
            if(cur.children[c - 'a'] == null) {
                return new ArrayList<>();
            }
            cur = cur.children[c - 'a'];
        }
        return cur.indices;
    }
}

class TrieNode {
    TrieNode[] children;
    List<Integer> indices;
    
    public TrieNode() {
        children = new TrieNode[26];
        indices = new ArrayList<>();
    }
}

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

Follow up

Previous784. Letter Case Permutation Next791. Custom Sort String

Last updated 4 years ago

/** * Time complexity : * Space complexity : */ class WordFilter { private Trie forward; private Trie backward; public WordFilter(String[] words) { forward = new Trie(true); backward = new Trie(false); for(int i = 0; i < words.length; i++) { forward.addWord(words[i], i); backward.addWord(words[i], i); } } public int f(String prefix, String suffix) { List<Integer> l1 = forward.startsWith(prefix); List<Integer> l2 = backward.startsWith(suffix); int i1 = l1.size() - 1; int i2 = l2.size() - 1; while(i1 >= 0 && i2 >= 0) { int a = l1.get(i1); int b = l2.get(i2); if(a > b) { i1--; } else if(a < b) { i2--; } else { return a; } } return -1; } } class Trie { TrieNode root; boolean forward; public Trie(boolean fwd) { root = new TrieNode(); forward = fwd; } public void addWord(String word, int idx) { TrieNode cur = root; for(int i = 0; i < word.length(); i++) { char c = this.forward ? word.charAt(i): word.charAt(word.length()-i-1); if(cur.children[c - 'a'] == null) { cur.children[c - 'a'] = new TrieNode(); } cur = cur.children[c - 'a']; cur.indices.add(idx); } } public List<Integer> startsWith(String word) { TrieNode cur = root; for(int i = 0; i < word.length(); i++) { char c = this.forward ? word.charAt(i): word.charAt(word.length()-i-1); if(cur.children[c - 'a'] == null) { return new ArrayList<>(); } cur = cur.children[c - 'a']; } return cur.indices; } } class TrieNode { TrieNode[] children; List<Integer> indices; public TrieNode() { children = new TrieNode[26]; indices = new ArrayList<>(); } } /** * Your WordFilter object will be instantiated and called as such: * WordFilter obj = new WordFilter(words); * int param_1 = obj.f(prefix,suffix); */

hashtagDescription

hashtagConstraints

hashtagApproach

hashtagLinks

hashtagExamples

hashtagSolutions

hashtagFollow up