Created
March 6, 2020 05:26
-
-
Save phongngtuan/44f503c72283bd7eefe7a37c77cddef3 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class TrieNode: | |
| def __init__(self, c: str, path: str): | |
| self.c = c # type: str | |
| self.counter = 0 # type: str | |
| self.path = path # type: str | |
| self.children = dict() # type: Dict[str, TrieNode] | |
| def add(self, key: str, path: str): | |
| if len(key) == 0: | |
| self.counter += 1 | |
| return None | |
| next_c = key[0] | |
| if next_c not in self.children: | |
| self.children[next_c] = TrieNode(next_c, path + next_c) | |
| self.children[next_c].add(key[1:], path + next_c) | |
| def find(self, key: str): | |
| if len(key) == 0: | |
| return self | |
| if key[0] not in self.children: | |
| return None | |
| return self.children[key[0]].find(key[1:]) | |
| def leaves(self): | |
| result = [] | |
| if self.counter > 0: | |
| result.append(self.path) | |
| for child in self.children.values(): | |
| result += child.leaves() | |
| return result | |
| class Solution: | |
| def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]: | |
| root = TrieNode("", "") | |
| for word in products: | |
| root.add(word, "") | |
| result = [] | |
| node = root | |
| for c in searchWord: | |
| if node is not None: | |
| node = node.find(c) | |
| if node is not None: | |
| result.append(sorted(node.leaves())[:3]) | |
| else: | |
| result.append([]) | |
| return result |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment