Leetcode: Prefix and Suffix Search

Posted on July 21, 2018September 10, 2019 by braindenny

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:

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);
 */

Post Views: 1