🎨Now live: Try our Free AI Image Generation Feature

Intuition
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.
Approach
- Edge Case Handling:
- If the input array
strs
is empty, return an empty string immediately. - Initialization: - Set the initial prefix to the first string in the array. This is the longest potential prefix we can have.
- Iterative Comparison: - Iterate through each string in the array starting from the second string. - While the current string does not start with the current prefix: - Shorten the prefix by removing the last character. - If the prefix becomes empty, return an empty string as there is no common prefix.
- Return Result: - After iterating through all strings, the remaining prefix is the longest common prefix.
Complexity
Time Complexity:
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.
Space Complexity:
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.
Code
C++
#include
#include
using namespace std;
class Solution {
public:
string longestCommonPrefix(vector& 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;
}
};
Python
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
Java
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;
}
}
JavaScript
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;
};