July 27, 2025 - Daily Drill¶

🎯 Daily Goals¶

📝 What I learned:¶

Trie ¶

Definition¶

Trie is a special form a Nary tree that stores strings. Each node represents a prefix. And each edges represent a character that helps you transit between prefix node to another.

From the above definition we can tell that any nodes that share the same parent has the same prefix.

how a string is stored in trie

Notice the string is not stored in any of the nodes. Instead it is stored as a path to certain nodes.

Implement Trie Node¶

class TrieNode:

    def __init__(self):
        self.links = [None] * 26
        self.is_word = False

    def get_idx(self, char):
        return ord(char.lower()) - ord("a")

    def get(self, char):
        return self.links[self.get_idx(char)]

    def put(self, char):
        self.links[self.get_idx(char)] = TrieNode()

    def has(self,char):
        return self.links[self.get_idx(char)] is not None

    def is_word(self):
        return self.is_word

    def set_word(self):
        self.is_word = True

Implement Trie¶

class Trie:

    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        cur = self.root
        for char in word:
            if cur.has(char):
                cur = cur.get(char)
            else:
                cur.put(char)
                cur = cur.get(char)
        cur.set_end()

    def _search_prefix(self, prefix):
        cur = self.root
        for char in prefix:
            if cur.has(char):
                cur = cur.get(char)
            else:
                return None
        return cur

    def search(self, word):
        node = self._search_prefiex(word)
        return node and node.is_end()

    def starts_with(self, prefix):
        return self._search_prefix(word) is not None

Key Takeaway¶

To implement the neighbors or links of TrieNode we can actually use a list with 26 elements to represent a - z. Then we can use ord(char) - ord('a') to quickly route the path.
Notice, we need to have a is_word attribute in the TrieNode since it does not distinguish between prefixes and an actual word after insertion.

This question is essentially a practice for Trie. We can iterate through each character and during each iteration, we keep track of what is the current segment is and where we are in the trie. For a new candidate, we check if hte trie has a link to an existing node that represnt the new character. If not we append the current segment to the result and reset the current segement and the node.

Implementation¶

def get_idx(char):
    return ord(char) - ord("a")

class TrieNode:
    def __init__(self):
        self.links = [None] * 26

    def has(self, char):
        return self.links[get_idx(char)] is not None

    def get(self, char):
        return self.links[get_idx(char)]

    def put(self, char):
        self.links[get_idx(char)] = TrieNode()

class Solution:
    def partitionString(self, s: str) -> List[str]:
        root = TrieNode()
        node = root
        ret = []
        cur_seg = []
        for c in s:
            cur_seg.append(c)
            if node.has(cur_seg[-1]):
                node = node.get(cur_seg[-1])
            else:
                node.put(cur_seg[-1])
                ret.append("".join(cur_seg))
                node = root
                cur_seg = []
        return ret

Complexity Analysis¶

Let the lenght of the string be n

Time Complexity: O(n)
Space Complexity: O(n)

We iterate through each character and performed some constant time action to it. Only non constant action would be the "".join() However, if we think in terms of each character, we would realize each character only contributed once to the loop of the join method. Thus it is still O(n) time. For space, since we are maintaining a trie. Each character would be stored in the worst case. And we are keep a current segment list as well.

🚀 Resources that Requires Further Study¶

Pillar AI security