14. Longest Common Prefix

Time: O(n*m)

Space: O(n*m)

Intuition

The longest common prefix of all strings cannot be longer than the shortest string, and it must be a prefix of every string. Vertical scanning: check each character position across all strings simultaneously, stopping at the first mismatch.

Algorithm

1If the array is empty, return "".
2Iterate column index i from 0 to strs[0].Length-1.
3For each string s in strs: if i >= s.Length or s[i] != strs[0][i], return strs[0][0..i] (exclusive).
4Return strs[0] (all strings are equal).

Example Walkthrough

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

1.i=0: f==f==f . i=1: l==l==l . i=2: o==o, but "flight"[2]=i != o. Stop.
2.Return strs[0][0..2] = "fl".

Output: "fl"

Common Pitfalls

•Check i >= s.Length BEFORE accessing s[i] to avoid IndexOutOfRange on shorter strings.

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?