Easy

题目描述

给定两个字符串 a 和 b，返回这两个字符串中最长的特殊序列的长度。如果不存在，则返回 -1。

两个字符串的特殊序列是指：该序列是其中一个字符串的子序列，但不是另一个字符串的子序列。

示例 1：

输入：a = "aba", b = "cdc"
输出：3
解释：最长的特殊序列是 "aba"，因为 "aba" 是 "aba" 的子序列，但不是 "cdc" 的子序列。
注意，"cdc" 也是一个最长的特殊序列。

示例 2：

输入：a = "aaa", b = "bbb"
输出：3
解释：最长的特殊序列是 "aaa" 和 "bbb"。

示例 3：

输入：a = "aaa", b = "aaa"
输出：-1
解释：字符串 a 的任何子序列也是字符串 b 的子序列。同样，字符串 b 的任何子序列也是字符串 a 的子序列。所以答案是 -1。

提示：

  • 1 <= a.length, b.length <= 100
  • a 和 b 由小写英文字母组成

解题思路

这道题看起来复杂，实际上是一道脑筋急转弯题目。我们需要理解"特殊序列"的定义：一个序列是其中一个字符串的子序列，但不是另一个字符串的子序列。

核心思路：

  1. 如果两个字符串相等：任何一个字符串的子序列都必然是另一个字符串的子序列，因此不存在特殊序列，返回 -1。

  2. 如果两个字符串不相等：字符串 a 本身就是 a 的子序列，但由于 a ≠ b，所以 a 不可能是 b 的子序列。同理，字符串 b 也是特殊序列。因此最长特殊序列就是较长字符串的长度，即 max(a.length(), b.length())。

实际上，当 a ≠ b 时，两个字符串的长度必然相等或不等。无论哪种情况，答案都是两个字符串中较长的那个的长度。

这个解法的精妙之处在于：我们不需要真正去寻找子序列，只需要判断两个字符串是否相等即可。

代码实现

class Solution {
public:
    int findLUSlength(string a, string b) {
        if (a == b) {
            return -1;
        }
        return max(a.length(), b.length());
    }
};

class Solution:
    def findLUSlength(self, a: str, b: str) -> int:
        if a == b:
            return -1
        return max(len(a), len(b))

public class Solution {
    public int FindLUSlength(string a, string b) {
        if (a == b) {
            return -1;
        }
        return Math.Max(a.Length, b.Length);
    }
}

var findLUSlength = function(a, b) {
    return a === b ? -1 : Math.max(a.length, b.length);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(min(m,n))
空间复杂度O(1)

其中 m 和 n 分别为字符串 a 和 b 的长度。时间复杂度主要来自于字符串比较操作。

相关题目