Longest Common Prefix
Problem
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 "".
Vertical scan: pick character at column j from the first string, then check that every other string has the same character at column j. The first column where the check fails (or any string runs out of characters) is where the common prefix ends.
["forecast", "forensic", "forever"]"fore"def longest_common_prefix(words):
if not words:
return ""
for j in range(len(words[0])):
c = words[0][j]
for i in range(1, len(words)):
if j >= len(words[i]) or words[i][j] != c:
return words[0][:j]
return words[0]function longestCommonPrefix(words) {
if (words.length === 0) return "";
for (let j = 0; j < words[0].length; j++) {
const c = words[0][j];
for (let i = 1; i < words.length; i++) {
if (j >= words[i].length || words[i][j] !== c) {
return words[0].slice(0, j);
}
}
}
return words[0];
}class Solution {
public String longestCommonPrefix(String[] words) {
if (words.length == 0) return "";
for (int j = 0; j < words[0].length(); j++) {
char c = words[0].charAt(j);
for (int i = 1; i < words.length; i++) {
if (j >= words[i].length() || words[i].charAt(j) != c) {
return words[0].substring(0, j);
}
}
}
return words[0];
}
}string longestCommonPrefix(vector<string>& words) {
if (words.empty()) return "";
for (int j = 0; j < (int)words[0].size(); j++) {
char c = words[0][j];
for (int i = 1; i < (int)words.size(); i++) {
if (j >= (int)words[i].size() || words[i][j] != c) {
return words[0].substr(0, j);
}
}
}
return words[0];
}Explanation
A common prefix is a run of characters that every word shares at the start. The neat way to find it is a vertical scan: compare the words column by column instead of word by word.
We use the first word as our yardstick. For each column j, we grab its character c = words[0][j] and then check that every other word has the same character at that same position.
The moment one word disagrees — or is too short to even have a column j — the prefix cannot grow any further, so we return everything before that point: words[0][:j]. If we get all the way through the first word with no mismatch, the whole first word is the prefix.
Example: ["forecast", "forensic", "forever"]. Columns 0–3 give f, o, r, e and all match. At column 4 the first word has c but "forensic" has n, so we stop and return "fore".