521. 最长特殊序列 Ⅰ

转载自Leet Code

题目描述

给你两个字符串，请你从这两个字符串中找出最长的特殊序列。 「最长特殊序列」定义如下： 该序列为某字符串独有的最长子序列（即不能是其他字符串的子序列）。

子序列 可以通过删去字符串中的某些字符实现，但不能改变剩余字符的相对顺序。 空序列为所有字符串的子序列，任何字符串为其自身的子序列。 输入为两个字符串，输出最长特殊序列的长度。如果不存在，则返回 -1。

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

示例 2： >输入：a = "aaa", b = "bbb" >输出：3

示例 3： >输入：a = "aaa", b = "aaa" >输出：-1

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

---

思路

\(T(M,N) = O(min(M,N))\), \(S(M,N) = O(1)\)

字符串\(a\), \(b\) 共有三种情况： - \(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))\)。

{.line-numbers}

class MySolution521 
{
    public int findLUSlength(String a, String b) 
    {
    	if (a.length()!=b.length()) 
    		return Math.max(a.length(), b.length());
    	else if (a.length()==b.length()&&!a.equals(b)) 
			return a.length();
    	return -1;
    }
}