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 “”.
Example 1:
Input: strs = [“flower”,”flow”,”flight”]
Output: “fl”
Example 2:
Input: strs = [“dog”,”racecar”,”car”]
Output: “”
Explanation: There is no common prefix among the input strings.
Table of Contents
Longest Common Prefix Problem Solution
Problem Solution In Python
class Solution:
def longestCommonPrefix(self, strs):
if len(strs) == 0:
return ""
commonPrefix = strs[0]
for string in strs:
commonPrefix = self.findPrefix(commonPrefix,string)
return commonPrefix
def findPrefix(self,prefix, string):
while prefix is not "":
if string.startswith(prefix):
return prefix
else:
prefix = prefix[:-1]
return ""
Problem Solution In Java
class Solution {
public String longestCommonPrefix(String[] strs) {
if(strs.length == 0){
return "";
}
String pref = strs[0];
for(String s : strs){
int len = Math.min(pref.length(), s.length());
for(int i = len; i >= 0; i--){
if(pref.indexOf(s.substring(0, i)) == 0){
pref = s.substring(0, i);
break;
}
}
}
return pref;
}
}
Problem Solution In C++
class Solution {
public:
string longestCommonPrefix(vector<string>& strs)
{
if (strs.size() == 0)
return "";
int maxL = strs[0].length();
bool match = true;
int j = 0;
for (int i = 1; i < strs.size(); i++)
{
if ((strs[i]).length() == 0 || (strs[i])[0] != (strs[0])[0])
return "";
while (match && j < maxL && j < strs[i].length())
{
match = ((strs[i])[j] == (strs[0])[j]);
j++;
}
if (!match)
maxL = j - 1;
if (strs[i].length() < maxL)
maxL = strs[i].length();
j = 0;
match = true;
}
return strs[0].substr(0, maxL);
}
};
Problem Solution In C
char * longestCommonPrefix(char ** strs, int strsSize) {
if (strsSize == 0)
return "";
size_t strMaxLen;
int i, j;
char * prefix = malloc(sizeof(char) * 200);
strMaxLen = strlen(*strs);
for (i = 0; i < strMaxLen; i++) {
for (j = 1; j < strsSize; j++) {
if (strs[j][i] != strs[j-1][i]) {
*prefix = '\0';
return prefix - i;
}
}
*prefix = strs[0][i];
prefix++;
}
*prefix = '\0';
return prefix-i;
}