Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/745.html

745. Prefix and Suffix Search (Hard)

Given many words, words[i] has weight i.

Design a class WordFilter that supports one function, WordFilter.f(String prefix, String suffix). It will return the word with given prefix and suffix with maximum weight. If no word exists, return -1.

Examples:

Input:
WordFilter([“apple”])
WordFilter.f(“a”, “e”) // returns 0
WordFilter.f(“b”, “”) // returns -1

Note:

  1. words has length in range [1, 15000].
  2. For each test case, up to words.length queries WordFilter.f may be made.
  3. words[i] has length in range [1, 10].
  4. prefix, suffix have lengths in range [0, 10].
  5. words[i] and prefix, suffix queries consist of lowercase letters only.

Solution 1.

  • class Trie {
        Trie[] children = new Trie[26];
        List<Integer> indexes = new ArrayList<>();
    
        void insert(String word, int i) {
            Trie node = this;
            for (char c : word.toCharArray()) {
                c -= 'a';
                if (node.children[c] == null) {
                    node.children[c] = new Trie();
                }
                node = node.children[c];
                node.indexes.add(i);
            }
        }
    
        List<Integer> search(String pref) {
            Trie node = this;
            for (char c : pref.toCharArray()) {
                c -= 'a';
                if (node.children[c] == null) {
                    return Collections.emptyList();
                }
                node = node.children[c];
            }
            return node.indexes;
        }
    }
    
    class WordFilter {
        private Trie p = new Trie();
        private Trie s = new Trie();
    
        public WordFilter(String[] words) {
            for (int i = 0; i < words.length; ++i) {
                String w = words[i];
                p.insert(w, i);
                s.insert(new StringBuilder(w).reverse().toString(), i);
            }
        }
    
        public int f(String pref, String suff) {
            suff = new StringBuilder(suff).reverse().toString();
            List<Integer> a = p.search(pref);
            List<Integer> b = s.search(suff);
            if (a.isEmpty() || b.isEmpty()) {
                return -1;
            }
            int i = a.size() - 1, j = b.size() - 1;
            while (i >= 0 && j >= 0) {
                int c = a.get(i), d = b.get(j);
                if (c == d) {
                    return c;
                }
                if (c > d) {
                    --i;
                } else {
                    --j;
                }
            }
            return -1;
        }
    }
    
    /**
     * Your WordFilter object will be instantiated and called as such:
     * WordFilter obj = new WordFilter(words);
     * int param_1 = obj.f(pref,suff);
     */
    
  • class WordFilter {
    public:
        unordered_map<string, int> d;
    
        WordFilter(vector<string>& words) {
            for (int k = 0; k < words.size(); ++k) {
                string w = words[k];
                int n = w.size();
                for (int i = 0; i <= n; ++i) {
                    string a = w.substr(0, i);
                    for (int j = 0; j <= n; ++j) {
                        string b = w.substr(j, n - j);
                        d[a + "." + b] = k;
                    }
                }
            }
        }
    
        int f(string pref, string suff) {
            string key = pref + "." + suff;
            if (d.count(key)) return d[key];
            return -1;
        }
    };
    
    /**
     * Your WordFilter object will be instantiated and called as such:
     * WordFilter* obj = new WordFilter(words);
     * int param_1 = obj->f(pref,suff);
     */
    
  • class Trie:
        def __init__(self):
            self.children = [None] * 26
            self.indexes = []
    
        def insert(self, word, i):
            node = self
            for c in word:
                idx = ord(c) - ord("a")
                if node.children[idx] is None:
                    node.children[idx] = Trie()
                node = node.children[idx]
                node.indexes.append(i)
    
        def search(self, pref):
            node = self
            for c in pref:
                idx = ord(c) - ord("a")
                if node.children[idx] is None:
                    return []
                node = node.children[idx]
            return node.indexes
    
    
    class WordFilter:
        def __init__(self, words: List[str]):
            self.p = Trie()
            self.s = Trie()
            for i, w in enumerate(words):
                self.p.insert(w, i)
                self.s.insert(w[::-1], i)
    
        def f(self, pref: str, suff: str) -> int:
            a = self.p.search(pref)
            b = self.s.search(suff[::-1])
            if not a or not b:
                return -1
            i, j = len(a) - 1, len(b) - 1
            while ~i and ~j:
                if a[i] == b[j]:
                    return a[i]
                if a[i] > b[j]:
                    i -= 1
                else:
                    j -= 1
            return -1
    
    
    # Your WordFilter object will be instantiated and called as such:
    # obj = WordFilter(words)
    # param_1 = obj.f(pref,suff)
    
    
  • type Trie struct {
    	children [26]*Trie
    	indexes  []int
    }
    
    func newTrie() *Trie {
    	return &Trie{indexes: []int{} }
    }
    func (this *Trie) insert(word string, i int) {
    	node := this
    	for _, c := range word {
    		idx := c - 'a'
    		if node.children[idx] == nil {
    			node.children[idx] = newTrie()
    		}
    		node = node.children[idx]
    		node.indexes = append(node.indexes, i)
    	}
    }
    
    func (this *Trie) search(pref string) []int {
    	node := this
    	for _, c := range pref {
    		idx := c - 'a'
    		if node.children[idx] == nil {
    			return []int{}
    		}
    		node = node.children[idx]
    	}
    	return node.indexes
    }
    
    type WordFilter struct {
    	p *Trie
    	s *Trie
    }
    
    func Constructor(words []string) WordFilter {
    	p := newTrie()
    	s := newTrie()
    	for i, w := range words {
    		p.insert(w, i)
    		s.insert(reverse(w), i)
    	}
    	return WordFilter{p, s}
    }
    
    func (this *WordFilter) F(pref string, suff string) int {
    	a := this.p.search(pref)
    	b := this.s.search(reverse(suff))
    	if len(a) == 0 || len(b) == 0 {
    		return -1
    	}
    	i, j := len(a)-1, len(b)-1
    	for i >= 0 && j >= 0 {
    		if a[i] == b[j] {
    			return a[i]
    		}
    		if a[i] > b[j] {
    			i--
    		} else {
    			j--
    		}
    	}
    	return -1
    }
    
    func reverse(w string) string {
    	ww := []byte(w)
    	for i, j := 0, len(w)-1; i < j; i++ {
    		ww[i], ww[j] = ww[j], ww[i]
    		j--
    	}
    	return string(ww)
    }
    
    /**
     * Your WordFilter object will be instantiated and called as such:
     * obj := Constructor(words);
     * param_1 := obj.F(pref,suff);
     */
    

All Problems

All Solutions