Longest Common Prefix of Strings
Problem
Given a non-empty list of strings, return the longest prefix shared by every string. If they share nothing at the start, return the 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.
Input
["forecast", "forensic", "forever"]Output
"fore"def 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 commonPrefix(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 commonPrefix(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 commonPrefix(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];
}