Find the longest common prefix among an array of strings.
Problem Statement
Write a function to find the longest common prefix string amongst an array of strings.
If there is no common prefix, return an empty string `""`.
Examples
Input: strs = ["flower", "flow", "flight"]
Output: "fl"
Explanation: "fl" is the longest prefix shared by all strings.
Input: strs = ["dog", "racecar", "car"]
Output: ""
Explanation: No common prefix exists among all input strings.
Complexity
Time Complexity: O(S)
Space Complexity: O(1)
Hints
š” Hint 1:
Initialize prefix as the entire first string.
š” Hint 2:
For each subsequent string, shrink prefix from the right until it is a prefix of strs[i].
š” Hint 3:
If prefix becomes empty, return "" immediately.
Editorial & Approach
Problem Overview & Intuition
Start with strs[0] as the candidate prefix. As we iterate through subsequent strings, shorten the prefix from the end until strs[i].startsWith(prefix). If prefix becomes empty, there is no common prefix.
Step-by-Step Approach
- If
strs.length === 0, return"". - Initialize
prefix = strs[0]. - Loop through strings from index 1.
- While
strs[i].indexOf(prefix) !== 0: shortenprefix = prefix.slice(0, -1). - If
prefix === "", return"". - Return
prefix.
Optimal Implementation (JavaScript)
function longestCommonPrefix(strs) {
if (!strs.length) return "";
let prefix = strs[0];
for (let i = 1; i < strs.length; i++) {
while (strs[i].indexOf(prefix) !== 0) {
prefix = prefix.slice(0, -1);
if (!prefix) return "";
}
}
return prefix;
}Complexity Analysis
Time Complexity
O(S) where S is the sum of characters across all strings.
Space Complexity
O(1) auxiliary space.
Edge Cases & Corner Traps Handled
- No common prefix: returns "".
- All strings identical.
- Array of single string: returns that string.