力扣题:子序列-12.29

力扣题-12.29

[力扣刷题攻略] Re：从零开始的力扣刷题生活

力扣题1：522. 最长特殊序列 II

解题思想：首先将字符串列表按长度进行降序，然后对每个字符串进行判断是否是独有的子序列，因为短的字串可能是长的字串的子序列，但是长的字串肯定是短字串的独有的子序列，通过这个条件进行判断。

class Solution(object):
    def findLUSlength(self, strs):
        """
        :type strs: List[str]
        :rtype: int
        """
        strs.sort(key=len,reverse=True)
        for i in range(0,len(strs)):
            if not self.isSubSeqOfAnother(strs,i):
                return len(strs[i])
        return -1

    ## 检查给定索引（idx）处的字符串是否是列表中任何其他字符串的子序列。
    def isSubSeqOfAnother(self,strs,idx):
        for i in range(0,len(strs)):
            if i==idx:
                continue
            ## 判断到小于时之后的可以不用判断了
            if len(strs[i])<len(strs[idx]):
                break
            ## 判断是否是子序列
            if self.isSubSeq(strs[idx],strs[i]):
                return True
        return False

    ## 判断s1是否为s2的子序列
    def isSubSeq(self,s1,s2):
        p1,p2=0,0
        while p1<len(s1) and p2<len(s2):
            while p2<len(s2) and s2[p2]!=s1[p1]:
                p2+=1
            if p2<len(s2):
                p1+=1
            p2+=1
        return p1==len(s1)

class Solution {
public:
    int findLUSlength(vector<string>& strs) {
        std::sort(strs.begin(), strs.end(), [](const std::string& a, const std::string& b) {
            return a.length() > b.length();
        });
        for (int i = 0; i < strs.size(); ++i) {
            if (!isSubSeqOfAnother(strs, i)) {
                return strs[i].length();
            }
        }

        return -1;
    }
    bool isSubSeqOfAnother(vector<string>& strs,int idx){
        for(int i=0;i<strs.size();i++){
            if(i == idx){
                continue;
            }
            if(strs[i].length()<strs[idx].length()){
                break;
            }
            if(isSubSeq(strs[idx],strs[i])){
                return true;
            }
        }
        return false;
    }
    bool isSubSeq(string s1,string s2){
        int p1 = 0, p2 = 0;
        while(p1<s1.length() && p2<s2.length()){
            while(p2<s2.length() && s2[p2]!=s1[p1]){
                p2++;
            }
            if(p2<s2.length()){
                p1++;
            }
            p2++;
        }
        return p1==s1.length();
    }

};