Advertisement
hoangreal

Trie pins string matching

Oct 19th, 2024 (edited)
61
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 2.97 KB | Source Code | 0 0
  1. """
  2. There are two Inputs, one is string, and Array is all Pins (e.g. ["Trump is winning", "Nvidia is a scam", "More men more fun"...]), the other is a user's rules (e.g. ["Trump", "Nvidia", "Cars"]) If one rule is met, notify user. For the above examples, the first two will be notified.
  3. So this should be a problem of substring matching, because all the rules under this case are one word. I propose that you can parse first and then use trie to do it or rolling hash (of course, it can also be KM) P But the thread starter is not familiar with it and deliberately didn't say it) I proposed to use rolling hash, the worst case requires all the rules and there is a risk of collision, so I suggest using trie.
  4. """
  5.  
  6. class Trie:
  7.  
  8.     ### STEP 1 ###
  9.     @staticmethod
  10.     def hash(val):  # Unique and Immutable
  11.         return val
  12.  
  13.     ### STEP 2
  14.     class Node:
  15.         def __init__(self, val="", is_word_end=False):
  16.             self.val = val
  17.             self.is_word_end = is_word_end
  18.             self.children = {}
  19.  
  20.         def create_child(self, val, is_word_end=False):
  21.             key = Trie.hash(val)
  22.             if key in self.children:
  23.                 if is_word_end:
  24.                     self.children[key].is_word_end = True
  25.             else:
  26.                 # Creates a new Node instance
  27.                 self.children[key] = self.__class__(val, is_word_end)
  28.             return
  29.  
  30.         def move(self, val):
  31.             key = Trie.hash(val)
  32.             return self.children.get(key, None)
  33.  
  34.     ### STEP 3 ###
  35.     def __init__(self, inputs=[]):
  36.         self.root = self.Node()
  37.         for input_branch in inputs:
  38.             self.insert(input_branch)
  39.  
  40.     def insert(self, input_branch: str) -> None:
  41.         """Time Complexity: O(len(input_branch))"""
  42.         node = self.root
  43.         for i, val in enumerate(input_branch):
  44.            
  45.             # STEP 1: when is a node 'end of word'
  46.             if i == len(input_branch) - 1:
  47.                 node.create_child(val, True)
  48.            
  49.             elif input_branch[i + 1] == ' ':
  50.                 node.create_child(val, True)
  51.                
  52.             # STEP 2: Static
  53.             else:
  54.                 node.create_child(val, False)
  55.             node = node.move(val)
  56.         return
  57.    
  58.     def is_match(self, word: str) -> bool:
  59.         node = self.root
  60.         for char in word:
  61.             node = node.move(char)
  62.             if node is None:
  63.                 return False
  64.         return node.is_word_end == True
  65.  
  66. """
  67. Return indices of users being notified
  68. """
  69. def solve(pins_strings: list[str], user_strings: list[str]) -> list[int]:
  70.     answers = []
  71.    
  72.     trie = Trie(pins_strings)
  73.    
  74.     for i in range(len(user_strings)):
  75.         if trie.is_match(user_strings[i]):
  76.             answers.append(i)
  77.            
  78.     return answers
  79.  
  80. pins_strings = ["Trump is winning", "Nvidia is a scam", "More men more fun"]
  81. user_strings = ["Trump", "Nvidia", "Cars"]
  82. print(solve(pins_strings, user_strings))
Tags: pinterest
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement