Header Ad

Leetcode Longest Common Prefix problem solution

In this Leetcode Longest Common Prefix problem solution, we need to 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 "".

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


Post a Comment

0 Comments