LeetCode每日一题

题目来源：力扣（LeetCode）

522. 最长特殊序列II（中等）

贪心 双指针

题目描述

给定字符串列表 strs ，返回其中 最长的特殊序列 的长度。如果最长特殊序列不存在，返回 -1 。

特殊序列 定义如下：该序列为某字符串 独有的子序列（即不能是其他字符串的子序列）。

s 的 子序列可以通过删去字符串 s 中的某些字符实现。

  • 例如，"abc" 是 "aebdc" 的子序列，因为您可以删除"aebdc"中的字符"e"和"d"来得到 "abc" 。"aebdc"的子序列还包括"aebdc"、 "aeb" 和 "" (空字符串)等。

示例 1：

输入: strs = [“aba”,”cdc”,”eae”]
输出: 3

示例 2:

输入: strs = [“aaa”,”aaa”,”aa”]
输出: -1

提示:

  • $2 <= strs.length <= 50$
  • $1 <= strs[i].length <= 10$
  • $strs[i]$ 只包含小写英文字母

题解

问题转换，枚举字符串，判断子序列

问题转换：

原问题 => 找出字符串列表 strs 中最长的特殊序列 的长度。

假设某个字符串 strs[i] ，如果它的一个子序列sub是「特殊序列」，那么 strs[i]本身也是一个「特殊序列」。

如果 sub 没有在除了 strs[i] 之外的字符串中以子序列的形式出现过，那么即使给 sub 不断地添加字符，它也依旧不会出现。而 strs[i] 就是给 sub 添加若干个（可以为零个）字符得到的结果。即如果 strs[i] 存在特殊序列sub，那么 strs[i] 本身也是一个特殊序列。

即字符串列表 strs 中最长的特殊序列的长度为其中某一非子序列字符串 strs[i] 的长度或-1

新问题 => 判断列表strs 中的每一个字符串 strs[i] 是否为其他字符串 strs[j](i!=j) 的子序列。

思路：

使用一个双重循环，外层枚举每一个字符串 strs[i] 作为特殊序列，内层枚举每一个字符串 strs[j](i!=j)，判断 strs[i] 是否不为 strs[j] 的子序列即可。

要想判断 strs[i] 是否为 strs[j] 的子序列，可以使用贪心 + 双指针的方法：即初始时指针 $pt_{i}$ 和 $pt_{j}$ 分别指向两个字符串的首字符。如果两个字符相同，那么两个指针都往右移动一个位置，表示匹配成功；否则只往右移动指针 $pt_{j}$，表示匹配失败。如果 $pt_{i}$ 遍历完了整个字符串，就说明 strs[i] 是 strs[j] 的子序列。

在所有满足要求的 strs[i] 中，选出最长的那个返回其长度作为答案。如果不存在满足要求的字符串，那么返回 -1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def findLUSlength(self, strs: List[str]) -> int:
        # 判断s是否为t的子序列
        def is_subseq(s: str, t: str) -> bool:
            pt_s = pt_t = 0
            # 双指针滑动，如果s被滑动完，说明s中的字符均顺序出现在了t中，即s是t的子序列，否则s不是t的子序列
            while pt_s < len(s) and pt_t < len(t):
                if s[pt_s] == t[pt_t]:
                    pt_s += 1
                pt_t += 1
            return pt_s == len(s)
        
        ans = -1
        for i, s in enumerate(strs):
            check = True  # s是否为特殊序列
            for j, t in enumerate(strs):
                if i != j and is_subseq(s, t):
                    check = False  # 是子序列就不是特殊序列
                    break
            if check:
                ans = max(ans, len(s))
        
        return ans

复杂度分析

  • 时间复杂度：$O(n^{2}·l)$，其中 $n$ 是数组 $strs$ 的长度，$l$ 是字符串的平均长度。
  • 空间复杂度：$O(1)$