Longest Common Prefix
EasyShrink the candidate against each word
Compare the words letter by letter from the start and stop at the first place they differ.
The idea
Start with the first string as the prefix. For each following word, trim the prefix until it matches the start of that word. Whatever survives is common to all.
f
l
o
w
e
r
0
1
2
3
4
5
Step 1 of 4. Start with "flower" as the prefix, then trim it against each word. Values: f, l, o, w, e, r.
1/4
Optimal
timeO(n·m)spaceO(1)
Trim until every word agrees.
1let prefix = strs[0];2for (const w of strs) {3 while (!w.startsWith(prefix))4 prefix = prefix.slice(0, -1);5 if (!prefix) return "";6}7return prefix;Input
- array
- [f, l, o, w, e, r]
Memory
- prefix
- —
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- strs = ["flower","flow","flight"]
- Output:
- "fl"
- Explanation:
- They all start with "fl".
Example 2
- Input:
- strs = ["dog","car"]
- Output:
- ""
- Explanation:
- Nothing shared → empty string.
Example 3
- Input:
- strs = ["abc","abc"]
- Output:
- "abc"
- Explanation:
- Identical words share the whole thing.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.