如何找到最长特殊序列的长度？

本文共计559个文字，预计阅读时间需要3分钟。

522. 最长特殊序列 II思路：子序列，不是字符串，因此不需要注意是否连续。s的特殊序列可以通过删除字符串s中的一些字符来实现。题目要求给出一个字符串数组，在其中找出字符串s的子序列。

522. 最长特殊序列 II

思路：子序列，不是字串，所以不需要注意是否连续。s的特殊序列可以他通过删去字符串s中的某些字符实现。

题目翻译：给出一个字符串数组，在里面找出字符串满足当前字符串不是字符串数组中其他字符串的子序列，返回满足条件的字符串中 最长的字符串的长度

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

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

在所有满足的str[i]中，选出最长的那个，返回长度作为答案，如果不存在就返回-1

class Solution { public int findLUSlength(String[] strs) { int n = strs.length; int ans = -1; for (int i = 0; i < n; ++i) { //设置一个标志 boolean check = true; for (int j = 0; j < n; ++j) { //只要在其他的字符串中找到了它是子序列，那么就把标志记为false，退出循环 if (i != j && is_son(strs[i], strs[j])) { check = false; break; } } //在所有找到的“孤儿”中找最长的，赋值给ans。 if (check) { ans = Math.max(ans, strs[i].length()); } } return ans; } public boolean is_son(String s, String t) { //定义两个指针 int ptS = 0, ptT = 0; while (ptS < s.length() && ptT < t.length()) { if (s.charAt(ptS) == t.charAt(ptT)) { ++ptS; } ++ptT; } //返沪true或者false 如果等，则返回true return ptS == s.length(); } }

其实读懂题，也就没有那么难了。