Dare2Solve
The longest common prefix problem requires us to find the longest substring that appears at the start of all strings in a given array. The intuition here is to iteratively compare each string in the array to a potential prefix, shortening this prefix if necessary until it fits all strings.
Edge Case Handling:
strs
is empty, return an empty string immediately.Initialization:
Iterative Comparison:
Return Result:
O(n * m), where n
is the number of strings and m
is the length of the longest string. In the worst case, each string comparison involves checking all characters in the prefix.
O(1) additional space is used, not counting the input and output.
This approach efficiently determines the longest common prefix by iteratively refining a potential prefix.
#include <string>
#include <vector>
using namespace std;
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
if (strs.empty()) {
return "";
}
string ans = strs[0];
for (int i = 1; i < strs.size(); ++i) {
while (strs[i].find(ans) != 0) {
ans = ans.substr(0, ans.size() - 1);
if (ans.empty()) {
return "";
}
}
}
return ans;
}
};
from typing import List
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
if not strs:
return ""
ans = strs[0]
for i in range(1, len(strs)):
while not strs[i].startswith(ans):
ans = ans[:-1]
if not ans:
return ""
return ans
class Solution {
public String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0) {
return "";
}
String ans = strs[0];
for (int i = 1; i < strs.length; i++) {
while (!strs[i].startsWith(ans)) {
ans = ans.substring(0, ans.length() - 1);
if (ans.isEmpty()) {
return "";
}
}
}
return ans;
}
}
var longestCommonPrefix = function(strs) {
if (strs.length === 0) {
return '';
}
let ans = strs[0];
for (let i = 1; i < strs.length; i++) {
while (strs[i].indexOf(ans) !== 0) {
ans = ans.substring(0, ans.length - 1);
if (ans === '') {
return '';
}
}
}
return ans;
};