C++ Solution(3ms) by sort and check common sequence


  • 0
    C

    Firstly, sorting these strings by descending order of length. Strings with same length are in alphabetical order.
    eg. a, f, af, af, a --> af, af, a, a, f

    Secondly, skipping the strings occurring more than once. For each unique string, check if it is the common sequence of its previous strings.

    At last, if it is unique and uncommon sequence of previous, return its size. Otherwise, judging next string.

    static bool isLess(const string &a, const string &b)
    {
        if(a.size() == b.size())
            return (a < b);
        return (a.size() > b.size());
    }
    
    class Solution {
    public:
        int findLUSlength(vector<string>& strs){
            //Sorting strs primarily by the descending order of string length and
            //secondly by the order of alphabet.
            sort(strs.begin(), strs.end(), isLess);
                
            for(decltype(strs.size()) i = 0; i < strs.size(); ){
                //Find the first string diff with current
                auto j = i + 1;
                while(j < strs.size() && strs[j] == strs[i]){
                    ++j;
                }
                //There are same strings as strs[i]
                if(j > i+1){
                    i = j;
                    continue;
                }
                
                //If reach here strs[i] is unique.
                //Check if it is a common sequence of previous longer strings.
                decltype(i) k;
                for(k = 0; k < i; ++k){
                    if(isCommonSeq(strs[k], strs[i])){
                        ++i;
                        break;
                    }
                }
                if(k == i)
                    return static_cast<int>(strs[i].size());
            }
            
            return -1;
        }
        
    private:
        bool isCommonSeq(string &a, string &b)
        {
            //b must be no longer than a
            if(a.size() < b.size())
                swap(a, b);
                
            decltype(a.size()) aI, bI;
            for(aI = 0, bI = 0; aI < a.size() && bI < b.size(); ++aI){
                if(a[aI] == b[bI])
                    ++bI;
            }
            
            return (bI == b.size());
        }
    };
    

Log in to reply
 

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