Prefix and Suffix Search
Similar Problems:
- Tag: #trie, #inspiring
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:
- words has length in range [1, 15000].
- For each test case, up to words.length queries WordFilter.f may be made.
- words[i] has length in range [1, 10].
- prefix, suffix have lengths in range [0, 10].
- words[i] and prefix, suffix queries consist of lowercase letters only.
Github: code.dennyzhang.com
Credits To: leetcode.com
Leave me comments, if you have better ways to solve.
- Solution:
// Blog link: https://code.dennyzhang.com/prefix-and-suffix-search // Basic Ideas: Trie tree // // Complexity: type WordFilter struct { children map[rune]*WordFilter ch rune weight int } func Constructor(words []string) WordFilter { root := WordFilter{map[rune]*WordFilter{}, ' ', -1} for i, word := range words { word2 := word for j:= len(word); j>=0; j-- { ch := '#' if j != len(word) { ch = rune(word[j]) } word2 = fmt.Sprintf("%s%s", string(ch), word2) // Add word2 to the trie tree p := &root for _, ch := range word2 { q, ok := p.children[ch] if ok { if q.weight < i { q.weight = i } } else { q = &WordFilter{map[rune]*WordFilter{}, ch, i} p.children[ch] = q } p = q } } } return root } func (this *WordFilter) F(prefix string, suffix string) int { str := fmt.Sprintf("%s#%s", suffix, prefix) res := -1 p := this for _, ch := range str { q, ok := p.children[ch] if !ok { return -1 } res = q.weight p = q } return res } /** * Your WordFilter object will be instantiated and called as such: * obj := Constructor(words); * param_1 := obj.F(prefix,suffix); */
Share It, If You Like It.