일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
Tags
- Decorator
- Convert Sorted List to Binary Search Tree
- DWG
- attribute
- 운영체제
- 30. Substring with Concatenation of All Words
- Substring with Concatenation of All Words
- iterator
- 프로그래머스
- Regular Expression
- 파이썬
- Class
- data science
- 315. Count of Smaller Numbers After Self
- 43. Multiply Strings
- Python Implementation
- Protocol
- kaggle
- 109. Convert Sorted List to Binary Search Tree
- 컴퓨터의 구조
- 시바견
- 밴픽
- shiba
- t1
- 715. Range Module
- concurrency
- Generator
- LeetCode
- Python
- Python Code
Archives
- Today
- Total
Scribbling
LeetCode: 1032. Stream of Characters 본문
First thing I came out with was to use a trie data structure, as it helps us deal with characters efficiently.
class StreamChecker:
def __init__(self, words: List[str]):
self.trie = {}
for word in words:
node = self.trie
for char in word:
if char not in node:
node[char] = {}
node = node[char]
node['#'] = '#'
self.candidates = []
def query(self, letter: str) -> bool:
self.candidates.append(self.trie)
next_candidates = []
ret = False
for candidate in self.candidates:
if letter in candidate:
next_candidates.append(candidate[letter])
if '#' in candidate[letter]:
ret = True
self.candidates = next_candidates
return ret
# Your StreamChecker object will be instantiated and called as such:
# obj = StreamChecker(words)
# param_1 = obj.query(letter)
However, above code is very inefficient because it stores evey possible string that has the current letter in the middle of itself.
To avoid this, we have to make great use of the fact that the only thing we have to do is check whether there's a word that ends with the current letter.
So, we make a trie with reversed words and everytime query function is called we just go through the trie.
class StreamChecker:
def __init__(self, words: List[str]):
self.trie = {}
for word in words:
node = self.trie
for char in word:
if char not in node:
node[char] = {}
node = node[char]
node['#'] = '#'
self.candidates = []
def query(self, letter: str) -> bool:
self.candidates.append(self.trie)
next_candidates = []
ret = False
for candidate in self.candidates:
if letter in candidate:
next_candidates.append(candidate[letter])
if '#' in candidate[letter]:
ret = True
self.candidates = next_candidates
return ret
# Your StreamChecker object will be instantiated and called as such:
# obj = StreamChecker(words)
# param_1 = obj.query(letter)
'Computer Science > Coding Test' 카테고리의 다른 글
[Dynamic Programming] Practice Question (0) | 2023.04.14 |
---|---|
LeetCode: 2115. Find All Possible Recipes from Given Supplies (0) | 2022.05.03 |
LeetCode: 2034. Stock Price Fluctuation (0) | 2022.03.23 |
LeetCode: 715. Range Module (0) | 2022.03.18 |
LeetCode: 833. Find And Replace in String (0) | 2022.03.15 |