Longest Common Prefix

LeetCode 14 | Difficulty: Easy

Easy

Problem Description

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Example 1:

Input: strs = ["flower","flow","flight"]
Output: "fl"

Example 2:

Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

Constraints:

- `1 <= strs.length <= 200`

- `0 <= strs[i].length <= 200`

- `strs[i]` consists of only lowercase English letters if it is non-empty.

Topics: Array, String, Trie

---

Approach

Trie (Prefix Tree)

Build a tree where each edge represents a character, and paths from root represent prefixes. Enables O(L) prefix lookups where L is the word length.

When to use

Prefix matching, autocomplete, word search, longest common prefix.

String Processing

Consider character frequency counts, two-pointer approaches, or building strings efficiently. For pattern matching, think about KMP or rolling hash. For palindromes, expand from center or use DP.

When to use

Anagram detection, palindrome checking, string transformation, pattern matching.

---

Solutions

Solution 1: C# (Best: 179 ms)

Metric	Value
Runtime	179 ms
Memory	N/A
Date	2017-07-23

Solution

public class Solution {
    public string LongestCommonPrefix(string[] strs) {
        return CommonPrefix(strs, 0, strs.Length-1);
    }
    string CommonPrefix(string[] arr, int low, int high)
{
    if(low==high)
    return arr[low];

    if (high > low)
    {
        int mid = low + (high-low)/2;
        string str1 = CommonPrefix(arr,low, mid);
        string str2 = CommonPrefix(arr,mid+1, high);
        return CommonPrefixUtil(str1, str2);
    }
    return string.Empty;
}

string CommonPrefixUtil(string str1, string str2)
{
    int m = str1.Length;
    int n = str2.Length;
    StringBuilder sb = new StringBuilder();
    for (int i = 0, j=0; i < m && j < n; i++, j++)
    {
        if(str1[i] != str2[j])
        break;
        else sb.Append(str1[i]);
    }
    return sb.ToString();
}
}

---

Complexity Analysis

Approach	Time	Space
Trie	$O(L × n)$	$O(L × n)$

---

Interview Tips

Key Points

• Start by clarifying edge cases: empty input, single element, all duplicates.