#14
Longest Common Prefix
Easy Vertical scan
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Return the longest prefix shared by every string in the array, or "" if there is none.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: the longest start shared by all the words.
Why this works: compare column by column; stop at the first column where any word differs or ends.
Example: ["flower", "flow", "flight"]
col 0: f f f ✓, col 1: l l l ✓col 2: o o i ✗ → "fl"
✦Hints open one at a time
Compare character by character, column by column.
Stop at the first column where a string ends or differs.
↗Approach
Take the first string as reference. For each index i, check that every other string has the same character at i. The first failure gives the prefix length.
</>Solution (Java)
class Solution {
public String longestCommonPrefix(String[] strs) {
String first = strs[0];
for (int i = 0; i < first.length(); i++) {
char c = first.charAt(i);
for (int j = 1; j < strs.length; j++) {
if (i == strs[j].length() || strs[j].charAt(i) != c) {
return first.substring(0, i);
}
}
}
return first;
}
}!Common mistake
Forgetting that a shorter string can end before a mismatch — check the length first.
Complexity
- Time: O(total characters).
- Space: O(1) besides the output.
Topic: Strings
🎬 Episodes 16–20: video coming soon