Longest Common Prefix

Easy

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.

Examples

InputOutput
strs = ["flower","flow","flight"]"fl"
strs = ["dog","racecar","car"]""

Python Solution

def longest_common_prefix(strs: list[str]) -> str:
    if not strs:
        return ""
    prefix = strs[0]
    for s in strs[1:]:
        while not s.startswith(prefix):
            prefix = prefix[:-1]
            if not prefix:
                return ""
    return prefix

JavaScript Solution

function longestCommonPrefix(strs) {
  if (!strs.length) return "";
  let prefix = strs[0];
  for (let i = 1; i < strs.length; i++) {
    while (!strs[i].startsWith(prefix)) {
      prefix = prefix.slice(0, -1);
      if (!prefix) return "";
    }
  }
  return prefix;
}

Step-by-Step Explanation

  1. Start with the first string as the prefix.
  2. For each subsequent string, shorten the prefix until it matches.
  3. If prefix becomes empty, return immediately.

Complexity Analysis

TimeO(S) where S is sum of all characters
SpaceO(1)

Tags

StringTrie

Related Problems

Valid ParenthesesRoman to Integer

Related Tools

Regex Tester

All Problems

Two SumReverse a StringPalindrome CheckFizzBuzzBinary SearchReverse Linked ListMerge Two Sorted ArraysValid ParenthesesMaximum Subarray (Kadane's Algorithm)Remove Duplicates from Sorted ArrayNth Fibonacci NumberValid AnagramFirst Unique CharacterClimbing StairsRoman to IntegerBest Time to Buy and Sell StockContains DuplicateMove ZeroesIntersection of Two Arrays