# 208
class TrieNode(defaultdict):
def __init__(self):
self.terminal = False
self.default_factory = TrieNode
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word: str) -> None:
node = self.root
for char in word: node = node[char]
node.terminal = True
def search(self, word: str) -> bool:
node = self.root
for char in word:
if char not in node: return False
node = node[char]
return node.terminal
def startsWith(self, prefix: str) -> bool:
node = self.root
for char in prefix:
if char not in node: return False
node = node[char]
return True
# 1032
class TrieNode(defaultdict):
def __init__(self):
self.terminal = False
self.default_factory = TrieNode
class StreamChecker:
def __init__(self, words: List[str]):
self.root = self.TrieNode()
self.stream = []
for word in set(words):
node = self.root
for char in reversed(word): node = node[char]
node.terminal = True
def query(self, letter: str) -> bool:
self.stream.append(letter)
node = self.root
for char in reversed(self.stream):
if node.terminal: return True
if char not in node: return False
node = node[char]
return node.terminal
# 1166
class TrieNode(defaultdict):
def __init__(self, val = None):
self.val = val
self.default_factory = TrieNode
class FileSystem:
def __init__(self): self.root = TrieNode()
def createPath(self, path: str, value: int) -> bool:
node = self.root
levels = path.split('/')
parents = levels[:-1]
child = levels[-1]
for p in parents:
if p and p not in node: return False
node = node[p]
if child in node: return False
node = node[child]
node.val = value
return True
def get(self, path: str) -> int:
node = self.root
for p in path.split('/'):
if p not in node: return -1
node = node[p]
if node.val is None: return -1
return node.val
# 336
class TrieNode(defaultdict):
def __init__(self):
super().__init__(TrieNode)
self.word_idx = -1
self.list = []
class Solution:
def solution_trie(self, words: List[str]) -> List[List[int]]:
def partial_palindrome(w, l):
r = len(w) - 1
while l < r:
if w[l] != w[r]: return False
l += 1; r -= 1
return True
# populating the trie
root = TrieNode()
for i, word in enumerate(words):
node = root
reversed_word = word[::-1]
for j, char in enumerate(reversed_word):
if partial_palindrome(reversed_word, j): node.list.append(i)
node = node[char]
node.word_idx = i
pairs = []
# find the pairs
for i, word in enumerate(words):
node = root
for j, char in enumerate(word):
# case 3: word[j] is longer than a possible word[i]
if node.word_idx != -1 and partial_palindrome(word, j): pairs.append([i, node.word_idx])
if char not in node: break
node = node[char]
else:
# case 1: word[i] == word[j][::-1]
if node.word_idx not in [-1, i]: pairs.append([i, node.word_idx])
# case 2: word[i] is abc|sos word[j] cba
for k in node.list: pairs.append([i, k])
return pairs
def solution_trie_lazy(self, words: List[str]) -> List[List[int]]:
def partial_palindrome(w, l):
r = len(w) - 1
while l < r:
if w[l] != w[r]: return False
l += 1; r -= 1
return True
def dfs_gather(node):
partial_palindrome_list = []
stack = [(child, [char]) for char, child in node.items()]
while stack:
node, seqs = stack.pop()
if node.word_idx != -1 and partial_palindrome(seqs, 0): partial_palindrome_list.append(node.word_idx)
stack.extend([(child, seqs + [char]) for char, child in node.items()])
return partial_palindrome_list
# populating the trie
root = TrieNode()
for i, word in enumerate(words):
node = root
for char in reversed(word): node = node[char]
node.word_idx = i
pairs = []
# find the pairs
for i, word in enumerate(words):
node = root
for j, char in enumerate(word):
# case 3: word[j] is longer than a possible word[i]
if node.word_idx != -1 and partial_palindrome(word, j): pairs.append([i, node.word_idx])
if char not in node: break
node = node[char]
else:
# case 1: word[i] == word[j][::-1]
if node.word_idx not in [-1, i]: pairs.append([i, node.word_idx])
# case 2: word[i] is abc|sos word[j] cba
node.list = dfs_gather(node)
for k in node.list: pairs.append([i, k])
return pairs
palindromePairs = solution_trie_lazy # solution_trie
# 588
class TrieNode(defaultdict):
def __init__(self):
self.type = "path"
self.content = ""
self.default_factory = TrieNode
class FileSystem:
def __init__(self): self.root = TrieNode()
@staticmethod
def _split(path):
if path == "/": return [] # root dir
return path[1:].split("/") # sequence of sub dirs
def ls(self, path: str) -> List[str]:
node = self.root
for d in self._split(path):
if d not in node: return []
node = node[d]
if node.type == "file": return [path.split("/")[-1]]
return sorted(list(node.keys()))
def mkdir(self, path: str) -> None:
node = self.root
for d in self._split(path): node = node[d]
def addContentToFile(self, filePath: str, content: str) -> None:
node = self.root
for d in self._split(filePath): node = node[d]
node.type = "file"
node.content += content
def readContentFromFile(self, filePath: str) -> str:
node = self.root
for d in self._split(filePath): node = node[d]
return node.content
# 1948
class TrieNode(defaultdict):
def __init__(self):
self.dl = False
self.default_factory = TrieNode
def __hash__(self): return id(self) # somehow needed for objects subclassed from defaultdict to be hashbale
class Solution:
def deleteDuplicateFolder(self, paths):
root = TrieNode()
for path in sorted(paths):
node = root
for d in path: node = node[d]
pattern = defaultdict(list)
def dfs(node):
key = "(" + ''.join(c + dfs(nd) for c, nd in node.items()) + ")"
if key != "()": pattern[key].append(node)
return key
dfs(root)
for nodes in pattern.values():
if len(nodes) > 1:
for i in nodes: i.dl = True
result = []
def backtrack(path, node):
for c, nd in node.items():
if nd.dl: continue
path.append(c)
backtrack(path, nd)
path.pop()
if path: result.append(path.copy())
backtrack([], root)
return result
# 212
class TrieNode(defaultdict):
def __init__(self):
self.word = ""
self.default_factory = TrieNode
class Trie:
def __init__(self, words=None):
self.root = TrieNode()
if words:
for word in words:
self.insert(word)
def insert(self, word):
node = self.root
for char in word: node = node[char]
node.word = word
class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
nrow, ncol = len(board), len(board[0])
trie = Trie(words)
crossed = set()
def backtrack(node, r, c):
if node.word: crossed.add(node.word)
if 0 <= r < nrow and 0 <= c < ncol and board[r][c] in node:
char = board[r][c]
board[r][c] = 'X'
for rr, cc in [(r-1,c),(r+1,c),(r,c-1),(r,c+1)]:
backtrack(node[char], rr, cc)
board[r][c] = char
for r in range(nrow):
for c in range(ncol):
backtrack(trie.root, r, c)
return crossed
# 642
class AutocompleteSystem:
class TrieNode(defaultdict):
def __init__(self):
super().__init__(AutocompleteSystem.TrieNode)
self.indices = set()
def __init__(self, sentences: List[str], times: List[int]):
self.root = self.TrieNode()
self._init_query()
self.statistics = dict()
self.idx_to_sentence = dict()
for sentence, time in zip(sentences, times): self.insert(sentence, time)
def _init_query(self):
self.query = ''
self.trav = self.root
def insert(self, sentence, time=1):
statistics, idx_to_sentence = self.statistics, self.idx_to_sentence
# insert or update
if sentence in statistics: statistics[sentence][0] += time
else: statistics[sentence] = [time, len(statistics)]
# traverse trie and annotate node with sentence idx
i = statistics[sentence][1]
idx_to_sentence[i] = sentence
node = self.root
for char in sentence:
node = node[char]
node.indices.add(i)
def auto_complete(self, char, k=3):
node, statistics, idx_to_sentence = self.trav, self.statistics, self.idx_to_sentence
# traverse
if not node or char not in node:
self.trav = None
return []
node = node[char]
self.trav = node
# grab the matching sentences
matches = []
for i in node.indices:
sentence = idx_to_sentence[i]
freq = statistics[sentence][0]
matches.append([sentence, freq])
# top k query
matches = nsmallest(k, matches, key=lambda x: [-x[1], x[0]])
return [match[0] for match in matches]
def input(self, c: str) -> List[str]:
if c == '#':
self.insert(self.query)
self._init_query()
return []
self.query += c
return self.auto_complete(c)