最长特殊序列 II 图解题解

这道题到底在问什么

输入

strs=["aba","cdc","eae"]

输出

3 （三个串互不为对方子序列，最长 3）

输入

strs=["aaa","aaa","aa"]

输出

-1 （aaa 互为子序列，aa 也被包含）

最优解：一步一步想明白

1. 3记住「逐个串去比，被别人包含就淘汰，扛过所有人就特殊」，下面每一帧都在套它。
2. 4轮到第 0 个串 "aba" 当候选。逐个拿别的串去试：只要它是某个串的子序列就被淘汰，全扛住才算特殊。
3. 5t 的第 0 位 "c" 不是候选要找的 "a"，i 指针不动，j 继续右移找下一个。
4. 6t 的第 1 位 "d" 不是候选要找的 "a"，i 指针不动，j 继续右移找下一个。
5. 7t 的第 2 位 "c" 不是候选要找的 "a"，i 指针不动，j 继续右移找下一个。
6. 8整个 "cdc" 扫完了，"aba" 没能被它完整包含，"aba" 不是 "cdc" 的子序列。继续拿下一个串来比。
7. 9t 的第 0 位 "a" 正好等于候选要找的 "a"，命中！候选已匹配 1/3 个字符。
8. 10t 的第 1 位 "b" 正好等于候选要找的 "b"，命中！候选已匹配 2/3 个字符。
9. 11t 的第 2 位 "a" 正好等于候选要找的 "a"，命中！候选已匹配 3/3 个字符。"aba" 被 "aba" 完整包含了。
10. 12候选 "aba" 被 "aba" 完整包含，它不是独有的，整串标红淘汰。
11. 13轮到第 1 个串 "cdc" 当候选。逐个拿别的串去试：只要它是某个串的子序列就被淘汰，全扛住才算特殊。
12. 14t 的第 0 位 "a" 不是候选要找的 "c"，i 指针不动，j 继续右移找下一个。
13. 15t 的第 1 位 "b" 不是候选要找的 "c"，i 指针不动，j 继续右移找下一个。
14. 16t 的第 2 位 "a" 不是候选要找的 "c"，i 指针不动，j 继续右移找下一个。
15. 17整个 "aba" 扫完了，"cdc" 没能被它完整包含，"cdc" 不是 "aba" 的子序列。继续拿下一个串来比。
16. 18又一个 "aba"，和刚才比过的那个完全相同，"cdc" 的第一个字符 "c" 在里面照样找不到，直接跳过。
17. 19t 的第 0 位 "a" 不是候选要找的 "c"，i 指针不动，j 继续右移找下一个。
18. 20t 的第 1 位 "b" 不是候选要找的 "c"，i 指针不动，j 继续右移找下一个。
19. 21整个 "ab" 扫完了，"cdc" 没被它完整包含。所有对手都比完了，没人包含 "cdc"，准备判它是特殊序列。
20. 22候选 "cdc" 扛过了所有对手，谁也包不住它，它就是特殊序列！整串标绿，用它的长度 3 刷新答案为 3。
21. 23轮到第 2 个串 "aba" 当候选。逐个拿别的串去试：只要它是某个串的子序列就被淘汰，全扛住才算特殊。
22. 24t 的第 0 位 "a" 正好等于候选要找的 "a"，命中！候选已匹配 1/3 个字符。
23. 25t 的第 1 位 "b" 正好等于候选要找的 "b"，命中！候选已匹配 2/3 个字符。
24. 26t 的第 2 位 "a" 正好等于候选要找的 "a"，命中！候选已匹配 3/3 个字符。"aba" 被 "aba" 完整包含了。
25. 27候选 "aba" 被 "aba" 完整包含，它不是独有的，整串标红淘汰。
26. 28轮到第 3 个串 "ab" 当候选。逐个拿别的串去试：只要它是某个串的子序列就被淘汰，全扛住才算特殊。
27. 29t 的第 0 位 "a" 正好等于候选要找的 "a"，命中！候选已匹配 1/2 个字符。
28. 30t 的第 1 位 "b" 正好等于候选要找的 "b"，命中！候选已匹配 2/2 个字符。"ab" 被 "aba" 完整包含了。
29. 31候选 "ab" 被 "aba" 完整包含，它不是独有的，整串标红淘汰。
30. 32回看全程：两个 "aba" 互为子序列、"ab" 是 "aba" 的子序列，全被淘汰；只有 "cdc" 谁也包不住，它就是最长特殊序列，答案 3。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def findLUSlength(self, strs: List[str]) -> int:
        def check(s: str, t: str):
            i = j = 0
            while i < len(s) and j < len(t):
                if s[i] == t[j]:
                    i += 1
                j += 1
            return i == len(s)

        ans = -1
        for i, s in enumerate(strs):
            for j, t in enumerate(strs):
                if i != j and check(s, t):
                    break
            else:
                ans = max(ans, len(s))
        return ans

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int findLUSlength(vector<string>& strs) {
        int ans = -1;
        int n = strs.size();
        auto check = [&](const string& s, const string& t) {
            int m = s.size(), n = t.size();
            int i = 0;
            for (int j = 0; i < m && j < n; ++j) {
                if (s[i] == t[j]) {
                    ++i;
                }
            }
            return i == m;
        };
        for (int i = 0, j; i < n; ++i) {
            int x = strs[i].size();
            for (j = 0; j < n; ++j) {
                if (i != j && check(strs[i], strs[j])) {
                    x = -1;
                    break;
                }
            }
            ans = max(ans, x);
        }
        return ans;
    }
};

import java.util.*;
class Solution {
    public int findLUSlength(String[] strs) {
        int ans = -1;
        int n = strs.length;
        for (int i = 0, j; i < n; ++i) {
            int x = strs[i].length();
            for (j = 0; j < n; ++j) {
                if (i != j && check(strs[i], strs[j])) {
                    x = -1;
                    break;
                }
            }
            ans = Math.max(ans, x);
        }
        return ans;
    }

    private boolean check(String s, String t) {
        int m = s.length(), n = t.length();
        int i = 0;
        for (int j = 0; i < m && j < n; ++j) {
            if (s.charAt(i) == t.charAt(j)) {
                ++i;
            }
        }
        return i == m;
    }
}

复杂度

面试官可能追问