LeetCode-Day59(C++) 521. 最长特殊序列

521. 最长特殊序列 Ⅰ

给你两个字符串,请你从这两个字符串中找出最长的特殊序列。

「最长特殊序列」定义如下:该序列为某字符串独有的最长子序列(即不能是其他字符串的子序列)。

子序列 可以通过删去字符串中的某些字符实现,但不能改变剩余字符的相对顺序。空序列为所有字符串的子序列,任何字符串为其自身的子序列。

输入为两个字符串,输出最长特殊序列的长度。如果不存在,则返回 -1。

示例 1:

输入: "aba", "cdc"
输出: 3
解释: 最长特殊序列可为 "aba" (或 "cdc"),两者均为自身的子序列且不是对方的子序列。

示例 2:

输入:a = "aaa", b = "bbb"
输出:3

示例 3:

输入:a = "aaa", b = "aaa"
输出:-1

提示:

  1. 两个字符串长度均处于区间 [1 - 100]
  2. 字符串中的字符仅含有 'a'~'z'

方法二:简单解法 【通过】
算法

字符串 a 和 b 共有 3 种情况:

a=b。如果两个字符串相同,则没有特殊子序列,返回 -1。

length(a)=length(b) 且 a != b。例如:abc 和 abd。这种情况下,一个字符串一定不会是另外一个字符串的子序列,因此可以将任意一个字符串看作是特殊子序列,返回 length(a) 或 length(b)。

length(a) !=length(b)。例如:abcd 和 abc。这种情况下,长的字符串一定不会是短字符串的子序列,因此可以将长字符串看作是特殊子序列,返回 max(length(a),length(b))。

class Solution {
public:
    int findLUSlength(string a, string b) {
        if(a == b) return -1;
        else if(a.size() == b.size()) return a.size();
        return max(a.size(), b.size());
    }
};
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 夜莺2517阅读 127,779评论 1 9
  • 我是黑夜里大雨纷飞的人啊 1 “又到一年六月,有人笑有人哭,有人欢乐有人忧愁,有人惊喜有人失落,有的觉得收获满满有...
    陌忘宇阅读 8,634评论 28 53
  • 兔子虽然是枚小硕 但学校的硕士四人寝不够 就被分到了博士楼里 两人一间 在学校的最西边 靠山 兔子的室友身体不好 ...
    待业的兔子阅读 2,683评论 2 9
  • 信任包括信任自己和信任他人 很多时候,很多事情,失败、遗憾、错过,源于不自信,不信任他人 觉得自己做不成,别人做不...
    吴氵晃阅读 6,244评论 4 8