What is the running time of my code, is it M*ln(N)?


  • -4
    L

    Here is my code

      class Solution {
       public:
    string longestCommonPrefix(vector<string> &strs) {
        
        
        return Pre_help(strs,0,strs.size()-1);
    }
    
    string Pre_help(vector<string> &strs,int start, int end){
        if(start>end) return "";
        if(start==end) return strs[start];
        int mid=(start+end)/2;
        string s1=Pre_help(strs,start, mid);
        string s2=Pre_help(strs,mid+1, end);
        string res;
        int len=min(s1.size(),s2.size());
        for(int i=0;i<len;i++){
            if(s1[i]==s2[i]){
                res.push_back(s1[i]);
            }else{
                return res;
            }
        }
        return res;
    }
     };

  • 0
    L

    No, I think the worst case is O(NM). I had this thought as well until I did some math and found out it was still O(NM).


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.