LeetCode: Prefix and Suffix Search Posted on July 21, 2018July 26, 2020 by braindenny Prefix and Suffix Search Similar Problems: CheatSheet: Leetcode For Code Interview CheatSheet: Common Code Problems & Follow-ups 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: // 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); */ Post Views: 1