Longest Common Prefix

Easy

Problem

Given an array of strings, return the longest string that is a prefix of every one of them, or "" if there is none.

Example 1

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

Example 2

Input:  ["dog", "racecar", "car"]
Output: ""

Test cases

Case 1

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

Case 2

Input:    ["dog","racecar","car"]
Expected: ""

Case 3

Input:    ["ab","ab"]
Expected: "ab"

Case 4

Input:    ["alone"]
Expected: "alone"

Case 5

Input:    ["","b"]
Expected: ""

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution2 approaches

1. Vertical scan

Time O(N·M) chars totalSpace O(1)

Compare column 0 of every string, then column 1, … Stop at the first mismatch or shortest string end.

function longestCommonPrefix(strs) {
if (!strs.length) return '';
for (let i = 0; i < strs[0].length; i++) {
const c = strs[0][i];
for (const s of strs) if (i === s.length || s[i] !== c) return strs[0].slice(0, i);
}
return strs[0];
}

2. Sort, compare first and last

Time O(N log N · M)Space O(1)

After sorting, only the lexicographically smallest and largest strings matter.

function longestCommonPrefix(strs) {
if (!strs.length) return '';
strs.sort();
const a = strs[0], b = strs[strs.length - 1];
let i = 0;
while (i < a.length && a[i] === b[i]) i++;
return a.slice(0, i);
}