How do you find the longest common prefix among an array of strings?
SHORT ANSWER
Take the first string as the candidate prefix and shorten it until every other string starts with it. Return what is left, which may be an empty string.
Explain it simply
Think of brand names that start the same way, such as "flower", "flow" and "flight". They all begin with "fl". Start by assuming the whole first word is the shared start, then test it against each next word. When a word does not begin with it, chop one letter off the end and test again.
Example
js
function longestCommonPrefix(strs) {
if (strs.length === 0) return "";
let prefix = strs[0];
for (let i = 1; i < strs.length; i++) {
while (!strs[i].startsWith(prefix)) {
prefix = prefix.slice(0, -1);
if (prefix === "") return "";
}
}
return prefix;
}
console.log(longestCommonPrefix(["flower", "flow", "flight"])); // Output: fl
console.log(longestCommonPrefix(["dog", "racecar", "car"]) === ""); // Output: trueComplexity
Time O(S) where S is the total characters across all strings, space O(1).
What to say in the interview
"I start with the first string as the prefix and, for each other string, trim the prefix until that string starts with it. If it becomes empty I stop. Time is O(S), where S is the total number of characters, and extra space is O(1)."
Common mistakes
- Not handling an empty array.
- Comparing characters by index without checking string lengths.