Skip to main content

Design Search Autocomplete System

Question​

Describe an algorithm to design a search autocomplete system that, when given a query string, produces a list of suggested query strings based on previously entered queries.

Example 1
Input: 

sentences = ["i love you", "island", "ironman", "i love leetcode"], searchWord = "i"

Output: 

[ "i love you", "island", "i love leetcode" ]

Solution​

all//Design Search Autocomplete System.py


class AutocompleteSystem:
    def __init__(self, sentences, times):
        self.sentences = sentences
        self.times = times
        self.cursentence = ""

    def input(self, c):
        self.cursentence += c
        if c == "#":
            self.sentences.append(self.cursentence)
            self.times.append(1)
            self.cursentence = ""
            return []
        else:
            ans = []
            for i, sentence in enumerate(self.sentences):
                if sentence.startswith(self.cursentence):
                    ans.append((self.times[i], sentence))
            ans.sort(key=lambda x: (-x[0], x[1]))
            return [sentence for _, sentence in ans[:3]]