Longest Common Prefix Trie DSA Solution

Learning Outcome

After this lesson, you should be able to stop a prefix walk exactly when words branch or the shortest word ends.

Problem Statement

Given a list of strings, return the longest common prefix among them.

Input	Output	Why
`strs = ["flower","flow","flight"]`	`"fl"`	All strings start with fl, then flower and flow continue with o while flight continues with i.

Brute Force Approach

Try each possible prefix length and compare it with every string. This repeats character checks.

Optimized Approach

Insert the words into a trie, then walk from the root while the current node has exactly one child and is not a word end.

Exact Pseudocode

if strs is empty:
  return ""
insert every word into trie
node = root
prefix = ""
while node is not word end and node has exactly one child:
  move to the only child
  append that character
return prefix

Reference Code

class Solution:
    def longestCommonPrefix(self, strs):
        if not strs:
            return ""

        root = {}
        for word in strs:
            node = root
            for ch in word:
                node = node.setdefault(ch, {})
            node["#"] = True

        node = root
        prefix = []
        while "#" not in node and len(node) == 1:
            ch = next(iter(node))
            prefix.append(ch)
            node = node[ch]
        return "".join(prefix)

Sample Dry Run

Step	State	Result
Build paths	flower, flow, and flight share f then l	single branch continues
At fl	next children are o and i	branch found
Stop	prefix collected is fl	return fl
Shortest word case	If one word ends, stop there	avoid overrun

Complexity

Measure	Value	Reason
Time	O(total characters)	Each inserted character is processed, then the common prefix is walked once.
Space	O(total characters) for trie version	The trie stores all inserted character nodes.

Edge Cases

If the input list is empty, return empty string.
If any string is empty, the answer is empty string.
Stop on word end even when there is still one child.

Interview Checklist

Detect branching by child count.
Detect shortest-word boundary with isWord.
Return the prefix collected before branching.

FAQs

Why stop when a word ends?

The common prefix cannot be longer than the shortest word.

Can this be solved without a trie?

Yes. Repeatedly shrinking the prefix is simpler and uses less extra memory, while trie teaches the prefix-branch idea.

What is the core pattern?

Single-branch prefix traversal.

Longest Common Prefix: Single Branch Trie Pattern