【每日一题】522. 最长特殊序列 II

思路

由于数据量比较小，可以使用遍历的方法。最主要的就是按照题目中的定义，实现一个判断a字符串是否是b字符串的子串的方法。

• 选取当前字符串，遍历其他字符串，如果当前字符串是其他字符串中某一个的子串，跳过它，下一个
• 如果当前字符串不是其他任何字符串的子串，就用它的长度更新最大长度
• 返回最大长度即可

cpp实现

class Solution {
public:
    int findLUSlength(vector<string>& strs) 
    {
        // 判断某个序列是否是另一个序列的子序列（按照这里的定义）
        auto is_subseq = [](const string& a, const string& b)
        {
            std::cout<<"a="<<a<<", b="<<b<<std::endl;
            int pt_a=0, pt_b = 0;
            while(pt_a<a.size() && pt_b<b.size())
            {
                if(a[pt_a]==b[pt_b]) pt_a +=1;
                // pt_b始终都要前进
                pt_b +=1;
            }
            // 当循环结束的时候，看pt_a是否已经指完了
            if(pt_a == a.size()) return true;
            else return false;
        };

        int ans = -1;
        for(int i=0; i<strs.size(); ++i)
        {
            bool check = true;
            for(int j=0; j<strs.size(); ++j)
            {                
                if(i!=j)
                {
                    bool subseq_flag = is_subseq(strs[i], strs[j]);
                    std::cout<<"subseq="<<subseq_flag<<std::endl;
                    if (subseq_flag)
                    {
                        check = false;
                        break;
                        // 只要有一个false就不行
                    }
                }
            }
            if (check==true)
            {
                ans = std::max(ans, static_cast<int>(strs[i].size()));
            }
        }
        return ans;
};