Clean C++ O(n^2) with Explanation


  • 4

    Very naive solution. Find the max Len of a string that is has no common subsequence of any other string.

    class Solution {
    public:
        //This is used to determine if a has common subsequence in b
        bool hasCommon(string a,string b){
            int remine = a.size();
            int remine2 = b.size();
            for(;remine>0&&remine2>0;){
                int i = a.size()-remine;
                int j = b.size()-remine2;
                if(a.at(i) == b.at(j)){
                    remine--;remine2--;
                }else{
                    remine2--;
                }
            }
            return remine==0;
        }
        int findLUSlength(vector<string>& strs) {
            int maxLen = -1;
            for(int i = 0;i<strs.size();++i){
                int currentLen = strs[i].length();
                bool all = true;
                for(int j = 0;j<strs.size();++j){
                    if(i!=j&&hasCommon(strs[i], strs[j])){
                        all = false;
                        break;
                    }
                }
                if(all){
                    maxLen = maxLen<currentLen?currentLen:maxLen;
                }
            }
            return maxLen;
        }
    };
    

  • 0
    K

    Hi I think this solution is based on a presumption that the longest uncommon subsequence always should be a whole string in the vector. Is that true? How to prove it?


  • 1

    If a uncommon subsequence subseq is the subsequence of a string str, this means that subseq isn't contained in any other string. hence, the complet string str which is more "complicated" should neither be contained in any other string.


  • 1

    Doesn't look like O(n^2). But what do you mean with n?


  • 1

    This solution looks like it is O(n^2 * avg_length^2), where n is of num of strings and avg_length is the average length of all strings


  • 0

    @pinkfloyda Yes, you're right.


  • 0

    @StefanPochmann said in Clean C++ O(n^2) with Explanation:

    Doesn't look like O(n^2). But what do you mean with n?

    Yep, @pinkfloyda has nicely gaven the correction. Thanks. I haven't thought about the complexity of hasCommon


  • 1
    Z

    @pinkfloyda Should it be O(n^2*avg_length)? Assuming comparison O(avg_length).


Log in to reply
 

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