14. Longest Common Prefix

EasyView on LeetCode

String

Time: O(n*m)

Space: O(n*m)

Problem Overview

The longest common prefix is the deepest path in a trie where every inserted string still agrees.

Intuition

The longest common prefix is the deepest path in a trie where every inserted string still agrees. Build a trie from all strings, then walk from the root while each node has exactly one child and is not marked as the end of a shorter word. Stop at the first branch or word end — the characters collected along that single-child chain are the answer.

Algorithm

1Insert every string into a trie character by character.
2Track child count per node so you can detect branching quickly.
3From the root, repeatedly follow the only child while childCount == 1 and the node is not an end-of-word marker.
4Append each character along that chain to the answer builder.
5Stop when a node has 0 or 2+ children, or when a complete string ends before others diverge.
6Return the built prefix (empty string if the first character already differs).

Example Walkthrough

Input: ["flower","flow","flight"]

1.Insert all three strings into the trie: shared path f → l → o, then branch at the fourth character.
2.Walk from root: f (1 child), l (1 child), o (1 child).
3.At o, the next level has multiple children (w from "flow"/"flower", i from "flight") — stop.
4.Collected prefix = "fl".

Output: "fl"

Common Pitfalls

•Mark end-of-word on nodes; if the shortest string is a prefix of others (e.g. "a", "ab"), stop when you hit that end marker.
•Vertical scanning also works, but the trie version matches the C# solution and scales cleanly to prefix-search follow-ups.
•Empty input array should return "" immediately before building the trie.

14.cs

// Approach: Insert all strings into a trie, then walk the trie until a
// branching node or end-of-string is encountered.
// Time: O(n*m) Space: O(n*m)

public class Solution
{
    public string LongestCommonPrefix(string[] strs)
    {
        var trie = new Trie();

        foreach (string str in strs)
            trie.Insert(str);


        return trie.GetPrefix();
    }
}

public class Trie
{

    private static Node root;
    public Trie()
    {
        root = new Node();
    }

    public void Insert(string word)
    {
        Node node = root;
        foreach (char c in word)
        {
            if (!node.ContainsKey(c))
            {
                node.Add(c, new Node());
                node.childCount++;
                node.lastIndexes = c - 'a';
            }

            node = node.Get(c);
        }
        node.SetEnd();
    }

    public string GetPrefix()
    {
        Node node = root;
        StringBuilder sb = new StringBuilder();
        while (node.childCount == 1 && !node.IsEnd())
        {
            sb.Append((char)('a' + node.lastIndexes));
            node = node.Get(node.lastIndexes);
        }

        return sb.ToString();
    }
}

class Node
{
    Node[] links = new Node[26];
    bool flag = false;
    public int childCount = 0;
    public int lastIndexes;

    public bool ContainsKey(char ch)
    {
        return (links[ch - 'a'] != null);
    }

    public void Add(char ch, Node node)
    {
        links[ch - 'a'] = node;
    }

    public Node Get(char ch)
    {
        return links[ch - 'a'];
    }

    public Node Get(int ind)
    {
        return links[ind];
    }

    public void SetEnd()
    {
        flag = true;
    }

    public bool IsEnd()
    {
        return flag;
    }
}

Was this solution helpful?