Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- """
- 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.
- 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.
- """
- class Trie:
- ### STEP 1 ###
- @staticmethod
- def hash(val): # Unique and Immutable
- return val
- ### STEP 2
- class Node:
- def __init__(self, val="", is_word_end=False):
- self.val = val
- self.is_word_end = is_word_end
- self.children = {}
- def create_child(self, val, is_word_end=False):
- key = Trie.hash(val)
- if key in self.children:
- if is_word_end:
- self.children[key].is_word_end = True
- else:
- # Creates a new Node instance
- self.children[key] = self.__class__(val, is_word_end)
- return
- def move(self, val):
- key = Trie.hash(val)
- return self.children.get(key, None)
- ### STEP 3 ###
- def __init__(self, inputs=[]):
- self.root = self.Node()
- for input_branch in inputs:
- self.insert(input_branch)
- def insert(self, input_branch: str) -> None:
- """Time Complexity: O(len(input_branch))"""
- node = self.root
- for i, val in enumerate(input_branch):
- # STEP 1: when is a node 'end of word'
- if i == len(input_branch) - 1:
- node.create_child(val, True)
- elif input_branch[i + 1] == ' ':
- node.create_child(val, True)
- # STEP 2: Static
- else:
- node.create_child(val, False)
- node = node.move(val)
- return
- def is_match(self, word: str) -> bool:
- node = self.root
- for char in word:
- node = node.move(char)
- if node is None:
- return False
- return node.is_word_end == True
- """
- Return indices of users being notified
- """
- def solve(pins_strings: list[str], user_strings: list[str]) -> list[int]:
- answers = []
- trie = Trie(pins_strings)
- for i in range(len(user_strings)):
- if trie.is_match(user_strings[i]):
- answers.append(i)
- return answers
- pins_strings = ["Trump is winning", "Nvidia is a scam", "More men more fun"]
- user_strings = ["Trump", "Nvidia", "Cars"]
- print(solve(pins_strings, user_strings))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement