0521. Longest Uncommon Subsequence I

题目信息

题号:

0521

难度:

Easy

主题:

两个字符串、子序列、不公共、最大长度

原题:

LeetCode 0521

重点:

目标序列只需是其中一个字符串的子序列且不是另一个的子序列、两串相等时不存在答案

题目重述

给定两个字符串 a 和 b。寻找一个字符串,使它是 a 或 b 中至少一个字符串的子序列,但不是另一个字符串的子序列;返回这种“不公共子序列”的最大可能长度。

若不存在任何不公共子序列,返回 -1。当 a 与 b 完全相同时,二者拥有相同的全部子序列,因此答案为 -1;当二者不同时,较长字符串本身或任一不同的等长字符串可以作为候选。

自建示例

两个等长字符串不同:

输入:a = "aba",b = "cdc"
输出:3
解释:字符串 "aba" 是自身的子序列,但不是 "cdc" 的子序列,因此可取得长度 3。

两个字符串完全相同:

输入:a = "xy",b = "xy"
输出:-1
解释:任意一个字符串的子序列也必然是另一个的子序列。

不相等时直接取较长字符串

若 a 与 b 相等,它们的子序列集合完全相同,不存在不公共子序列。若二者不相等,较长字符串不可能成为较短字符串的子序列,因此它自身就是合法候选;若长度相等,不同字符串也不可能互为子序列,取其长度即可。

C++ 实现

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

代码分析

相等性决定了是否存在候选;不等时较长串或等长的任一串都满足“不被另一个串包含”,而任何子序列长度都不超过原串长度,所以该长度同时是上界和可达值。时间复杂度为 O(|a|+|b|),额外空间复杂度为 O(1)。