golang solution


  • 0
    C
    type AutocompleteSystem struct {
        Root *Node
        Curr *Node
        Pre string
    }
    
    type Node struct {
        R []string
        Can map[string]int
        Next []*Node
    }
    
    func Constructor(sentences []string, times []int) AutocompleteSystem {
        var res AutocompleteSystem
        res.Root = &Node{}
        res.Curr = res.Root
        
        for i,s := range sentences {
            res.addSentence(s, times[i])
        }
        
        return res
    }
    
    func getIndex(c byte) int {
        if c == ' ' {
            return 26
        } 
        return int(c - 'a')
    }
    
    func (this *AutocompleteSystem) addSentence(s string, times int) {
        curr := this.Root
        for i := range s {
            if curr.Next == nil {
                curr.Next = make([]*Node, 27)
            }
            index := getIndex(s[i]) 
            if curr.Next[index] == nil {
                curr.Next[index] = &Node{}
            }
                
            curr = curr.Next[index]
            
            if curr.Can == nil {
                curr.Can = make(map[string]int)
            }
            curr.Can[s] += times
            // remove existing one
            for k := range curr.R {
                if curr.R[k] == s {
                    curr.R = append(curr.R[:k], curr.R[k+1:]...)
                    break
                }
            }
            
            // add
            k := 0
            for ;k < len(curr.R);k++ {
                if curr.Can[s] > curr.Can[curr.R[k]] || (curr.Can[s] == curr.Can[curr.R[k]] && s < curr.R[k]) {
                    break
                }
            }
            curr.R = append(curr.R[:k], append([]string{s}, curr.R[k:]...)...)
            if len(curr.R) > 3 {
                curr.R = curr.R[:3]
            }
        }
    }
    
    func (this *AutocompleteSystem) Input(c byte) []string {
        var res []string
        if c == '#' {
            this.addSentence(this.Pre, 1)
            this.Curr = this.Root
            this.Pre = ""
            return res
        }
        this.Pre = this.Pre + string(c)
        if this.Pre == "wo" {
            fmt.Println("1")
        }
        index := getIndex(c)
        if this.Curr == nil || this.Curr.Next == nil || this.Curr.Next[index] == nil {
            this.Curr = nil
            return res
        }
    
        this.Curr = this.Curr.Next[index]
        return this.Curr.R
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.