522. 最长特殊序列 II

题目描述：

给定字符串列表 strs ，返回其中 最长的特殊序列 的长度。如果最长特殊序列不存在，返回 -1 。

特殊序列 定义如下：该序列为某字符串 独有的子序列（即不能是其他字符串的子序列）。

s 的 子序列 可以通过删去字符串 s 中的某些字符实现。

• 例如， "abc" 是 "aebdc" 的子序列，因为您可以删除 "aebdc" 中的下划线字符来得到 "abc" 。 "aebdc" 的子序列还包括 "aebdc"、 "aeb" 和 "" (空字符串)。

示例 1：

输入: strs = ["aba","cdc","eae"]
输出: 3

示例 2:

输入: strs = ["aaa","aaa","aa"]
输出: -1

提示:

• 2 <= strs.length <= 50
• 1 <= strs[i].length <= 10
• strs[i] 只包含小写英文字母

---

解题分析及思路：

方法：枚举

思路： 对于给定的某个字符串 str[i]，如果它的一个子序列 sub 是「特殊序列」，那么 str[i] 本身也是一个「特殊序列」。

这是因为如果 sub 没有在除了 str[i] 之外的字符串中以子序列的形式出现过，那么给 sub 不断地添加字符，它也不会出现。而 str[i] 就是 sub 添加若干个（可以为零个）字符得到的结果。

因此我们只需要使用一个双重循环，外层枚举每一个字符串 str[i] 作为特殊序列，内层枚举每一个字符串 str[j] (i ! =j)，判断 str[i] 是否不为 str[j] 的子序列即可。

要想判断 str[i] 是否为 str[j] 的子序列，我们可以使用贪心 + 双指针的方法：即初始时指针 pt i ​ 和 pt j ​ 分别指向两个字符串的首字符。如果两个字符相同，那么两个指针都往右移动一个位置，表示匹配成功；否则只往右移动指针 pt j ​ ，表示匹配失败。如果 pt i ​ 遍历完了整个字符串，就说明 str[i] 是 str[j] 的子序列。

在所有满足要求的 str[i] 中，我们选出最长的那个，返回其长度作为答案。如果不存在满足要求的字符串，那么返回 −1。

package leetcode

// judge whether s is a subsequence of t
func isSubseq(s, t string) bool {
	i := 0
	for _, c := range t {
		if s[i] == byte(c) {
			i++
			if i == len(s) {
				return true
			}
		}
	}
	return false
}

// judge whether strs[index] is a subsequence of other strings
func hasSubSeq(index int, strs []string) bool {
	for j, t := range strs {
		if j != index && isSubseq(strs[index], t) {
			return false
		}
	}
	return true
}

func findLUSlength(strs []string) int {
	ans := -1
	for i, s := range strs {
		if len(s) <= ans {
			continue
		}
		if hasSubSeq(i, strs) {
			ans = len(strs[i])
		}
	}
	return ans
}

复杂度：

• 时间复杂度：O(N² * L)，其中 N 是数组 strs 的长度，L 是字符串的平均长度。
• 空间复杂度：O(1)

执行结果：

• 执行耗时:0 ms,击败了100.00% 的Go用户
• 内存消耗:2.1 MB,击败了88.89% 的Go用户