1268. Search Suggestions System - LeetCode Solution


Trie String Binary Search

Python Code:

class Trie:
    def __init__(self, flag = False):
        self.letters = [0] * 27
        self.flag = flag
        
        
        
class Solution:
    def addProducts(self, word, root):
        for letter in word:
            if root.letters[ord(letter) - 97]:
                root = root.letters[ord(letter) -97]
            else:
                root.letters[ord(letter) - 97] = Trie()
                root = root.letters[ord(letter) - 97]
        root.flag = True
        
    def search(self, root, creating):
        a = []
        if not root:
            return a
        if root.flag:
            a.append(creating)
        
        for i in range(len(root.letters)):
            if root.letters[i]:
                a += self.search(root.letters[i], creating + chr(i + 97) )
        return a
            
        
    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
        root = Trie()
        
        ans = []
        for product in products:
            self.addProducts(product, root)
            
        for i in range(len(searchWord)):
            root_ptr = root
            for letter in searchWord[0: i+1]:
                ind = ord(letter) - 97
                root_ptr = root_ptr.letters[ind]
                if not root_ptr:
                    break
                    
            a = self.search(root_ptr, searchWord[0:i+1])
       
            a.sort()
            ans.append(a[:3])
        return ans


Comments

Submit
0 Comments
More Questions

133B - Unary
1547A - Shortest Path with Obstacle
624A - Save Luke
1238A - Prime Subtraction
1107C - Brutality
1391B - Fix You
988B - Substrings Sort
312A - Whose sentence is it
513A - Game
1711E - XOR Triangle
688A - Opponents
20C - Dijkstra
1627D - Not Adding
893B - Beautiful Divisors
864B - Polycarp and Letters
1088A - Ehab and another construction problem
1177B - Digits Sequence (Hard Edition)
1155B - Game with Telephone Numbers
1284A - New Year and Naming
863B - Kayaking
1395B - Boboniu Plays Chess
1475D - Cleaning the Phone
617B - Chocolate
1051B - Relatively Prime Pairs
95B - Lucky Numbers
1692D - The Clock
1553D - Backspace
1670D - Very Suspicious
1141B - Maximal Continuous Rest
1341A - Nastya and Rice