0521. Longest Uncommon Subsequence I ==================================== 题目信息 -------- :题号: 0521 :难度: Easy :主题: 两个字符串、子序列、不公共、最大长度 :原题: `LeetCode 0521 `_ :重点: 目标序列只需是其中一个字符串的子序列且不是另一个的子序列、两串相等时不存在答案 题目重述 -------- 给定两个字符串 ``a`` 和 ``b``。寻找一个字符串,使它是 ``a`` 或 ``b`` 中至少一个字符串的子序列,但不是另一个字符串的子序列;返回这种“不公共子序列”的最大可能长度。 若不存在任何不公共子序列,返回 ``-1``。当 ``a`` 与 ``b`` 完全相同时,二者拥有相同的全部子序列,因此答案为 ``-1``;当二者不同时,较长字符串本身或任一不同的等长字符串可以作为候选。 自建示例 -------- 两个等长字符串不同: .. code-block:: text 输入:a = "aba",b = "cdc" 输出:3 解释:字符串 "aba" 是自身的子序列,但不是 "cdc" 的子序列,因此可取得长度 3。 两个字符串完全相同: .. code-block:: text 输入:a = "xy",b = "xy" 输出:-1 解释:任意一个字符串的子序列也必然是另一个的子序列。 不相等时直接取较长字符串 ------------------------ 若 ``a`` 与 ``b`` 相等,它们的子序列集合完全相同,不存在不公共子序列。若二者不相等,较长字符串不可能成为较短字符串的子序列,因此它自身就是合法候选;若长度相等,不同字符串也不可能互为子序列,取其长度即可。 C++ 实现 -------- .. code-block:: cpp 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)``。