# Leetcode: Prefix and Suffix Search

Prefix and Suffix Search

Similar Problems:

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.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

• Solution:
// 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.