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


If You Like This Page Then Make Sure To Follow Us on Facebook, G News and Subscribe Our YouTube Channel. We will provide you updates daily.
Shares
facebook sharing button Share
twitter sharing button Tweet
whatsapp sharing button Share
telegram sharing button Share
pinterest sharing button Pin

Leave a Comment