​LeetCode刷题实战522：最长特殊序列 II

示例：
输入: "aba", "cdc", "eae"
输出: 3

提示：
所有给定的字符串长度不会超过 10 。
给定字符串列表的长度将在 [2, 50 ] 之间。

class Solution {
public:
    bool checkSubSeq(string a, string b) { // 判断字符串a是否是字符串b的子序列
        for(int i = 0, j = 0; i < a.size(); ++i, ++j) {
            while(j < b.size() && a[i] != b[j]) { 
                ++j;
            } 
            if(j == b.size()) { // 如果b走到最后也没有和a匹配完，那么a不是b的子序列
                return false;
            }
        }
        return true;
    }

    int findLUSlength(vector<string>& strs) {
        sort(strs.begin(), strs.end(), [&](string a, string b) { // 将字符串数组按照字符串长度从大到小排序
            if(a.size() != b.size()) { 
                return a.size() > b.size();
            }
            return a < b;
        });
        for(int i = 0; i < strs.size(); ++i) { // 按照字符串长度从大到小枚举所有的字符串
            bool flag = true; // flag表示当前字符串是否是一个特殊序列
            if(i + 1 < strs.size() && strs[i] == strs[i + 1]) { // 如果存在和这个字符串相同的字符串，则这个字符串不是特殊序列
                flag = false;
                continue;
            }
            for(int j = 0; j < i; ++j) { // 枚举所有长度比当前字符串大的字符串，判断当前字符串是否是其他字符串的子序列
                if(checkSubSeq(strs[i], strs[j]) == true) {
                    flag = false;
                }
            }
            if(flag == true) { // 找到了一个特殊序列，它的长度就是答案 
                return strs[i].size(); 
            }
        }
        return -1;
    }
};