Longest Common Prefix
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: ""
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);}