Skip to content

Instantly share code, notes, and snippets.

Created March 26, 2023 16:54
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
What would you like to do?
LCP trie (trie with multi-character prefixes so nodes are 'common prefix' branches rather than common ancestor) adapted from dict trie in and mostly generated with GPT-3.5 by describing the algorithm as pseudo-code comments
class TrieNode(object):
def __init__(self): = {}
self.is_word = False
class Trie(object):
def __init__(self):
self.root = TrieNode()
def insert_lcp(self, word: str) -> None:
Inserts a word into the trie and aggregates it with existing nodes (longest
common prefix nodes).
node = self.root
# If no common ancestors, insert entire word
if not[word] = TrieNode()[word].is_word = True
# Iterate through existing nodes
while True:
# Find the longest common prefix between the word and node keys
lcp = ""
lcp_key = None
for key in
prefix = ""
for i, (a, b) in enumerate(zip(word, key)):
if a == b:
prefix += a
if len(prefix) > len(lcp):
lcp = prefix
lcp_key = key
if not lcp:
# No common prefix, insert entire word as new node[word] = TrieNode()[word].is_word = True
# If entire common ancestor is found, insert below
lcp_size = len(lcp)
if lcp == lcp_key:
node =[lcp_key]
word = word[lcp_size:]
# Split the node at the branch point and insert the rest of the word below it
new_node = TrieNode()[lcp] = new_node[lcp_key[lcp_size:]] =
if not word:
# The branch point is the word
new_node.is_word = True
# Put the remaining suffix below the LCP branch point node
partial_word = word[lcp_size:][partial_word] = TrieNode()[partial_word].is_word = True
def insert_char(self, word: str) -> None:
Inserts a word into the trie (char level nodes).
node = self.root
for letter in word:
child =
if not child:[letter] = TrieNode()
node =[letter]
node.is_word = True
def search(self, word: str) -> None:
Returns if the word is in the trie.
node = self.root
for letter in word:
node =
if not node:
return False
return node.is_word
def starts_with(self, prefix: str) -> bool:
Returns if there is any word in the trie
that starts with the given prefix.
node = self.root
for letter in prefix:
node =
if not node:
return False
return True
def get_start(self, prefix: str) -> list[str]:
Returns words started with prefix
def _get_key(pre, pre_node):
words_list = []
if pre_node.is_word:
for x in
words_list.extend(_get_key(pre + str(x),
return words_list
words = []
if not self.starts_with(prefix):
return words
return words
node = self.root
for letter in prefix:
node =
return _get_key(prefix, node)
def print_data(self) -> None:
def dfs(node, level):
if not node:
for key, child in
print(" " * level + key)
dfs(child, level + 1)
dfs(self.root, 0)
def walk(self):
def dfs(node):
if not node:
return {}
children = {}
for letter, child in
children[letter] = dfs(child)
return {"word": node.is_word, "children": children}
return dfs(self.root)
t = Trie()
strings = "all although allow alone altogether".split()
for s in strings:
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment