LeetCode 522 最长特殊序列II[枚举 双指针] HERODING的LeetCode之路

解题思路：
解题的关键在于特殊序列的长度除了-1，最小也是最短序列的长度，所以根本不需要考虑不同序列中子序列之间的匹配情况，这是因为最长序列（即序列本身）就是最特殊子序列。遍历所有的序列对，判断是否能匹配，不能匹配，更新最长序列长度，最后返回，代码如下：

class Solution {
public:
    int findLUSlength(vector<string>& strs) {
        int n = strs.size();
        int ans = -1;
        for(int i = 0; i < n; i ++) {
            bool check = true;
            for(int j = 0; j < n; j ++) {
                if(i != j && judge(strs[i], strs[j])) {
                    check = false;
                    break;
                }
            }
            if(check) {
                ans = max(ans, static_cast<int>(strs[i].size()));
            }
        }
        return ans;
    }

    bool judge(string s1, string s2) {
        int n1 = s1.size(), n2 = s2.size();
        // 长度相同比较是否相同
        if(n1 == n2) return s1 == s2;
        int index1 = 0, index2 = 0;
        // 长度不同比较是否子串
        while(index1 < n1 && index2 < n2) {
            if(s1[index1] == s2[index2]) {
                index1 ++;
            }
            index2 ++;
        }
        return index1 == n1;
    }

};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36