Longest Common Prefix Problem Solution

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.

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;
}