Skip to content

Prepare For Coder Interview – Denny

  • Basic
  • Medium
  • Hard
  • Architect
  • Life

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:

  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:
// 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);
 */
linkedin
github
slack

Post Views: 1
Posted in HardTagged #inspiring, #trie, redo

Post navigation

LeetCode: Design Circular Deque
LeetCode: Closest Leaf in a Binary Tree

Leave a Reply Cancel reply

Your email address will not be published.

Tags

#array #backtracking #bfs #binarytree #bitmanipulation #blog #classic #codetemplate #combination #dfs #dynamicprogramming #game #graph #greedy #heap #inspiring #interval #linkedlist #manydetails #math #palindrome #recursive #slidingwindow #stack #string #subarray #trie #twopointer #twosum binarysearch editdistance hashmap intervaldp knapsack monotone oodesign presum rectangle redo review rotatelist series sql treetraversal unionfind

Recent Posts

  • a
  • a
  • a
  • a
  • a

Recent Comments

    Archives

    Categories

    • Amusing
    • Basic
    • Easy
    • Hard
    • Life
    • Medium
    • Resource
    • Review
    • Series
    • Uncategorized
    Proudly powered by WordPress | Theme: petals by Aurorum.