Part 2 · Problems · Strings
Longest Common Prefix
#14 · Easy · LeetCode
Return the longest prefix shared by all strings.
["flower","flow","flight"] -> "fl" ["dog","racecar","car"] -> ""
Ask before coding
- Empty list returns empty string?
Hint
Check column by column across all strings.
Approach
For each index of the first string, check every string has the same character there. Stop at the first mismatch or the shortest string's end.
Time O(total characters) Space O(1)
Watch it run
Solution (JavaScript, tested)
function longestCommonPrefix(strs) {
if (strs.length === 0) return "";
for (let i = 0; i < strs[0].length; i++) {
for (const s of strs) {
if (i >= s.length || s[i] !== strs[0][i]) return strs[0].slice(0, i);
}
}
return strs[0];
}Traps
- Running past a shorter string's end.
Say out loud: Vertical scan, column by column, stop at the first mismatch.