子序列 392、524、521、522

392. 判断子序列（简单）

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

进阶：

如果有大量输入的 S，称作 S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

致谢：

特别感谢 @pbrother 添加此问题并且创建所有测试用例。

示例 1：
输入：s = "abc", t = "ahbgdc"
输出：true
示例 2：
输入：s = "axc", t = "ahbgdc"
输出：false
提示：

0 <= s.length <= 100
0 <= t.length <= 10^4
两个字符串都只由小写字符组成。

解法一、双指针遍历

等于一个挪一下。如果s真的是很多个字符串，只需要引出一个数组，来当作指针，时间复杂度依旧是O（n）（t的长度）。

class Solution {public static boolean isSubsequence(String s, String t) {int p = 0;int lenS = s.length(),lenT = t.length();if(lenS > lenT||lenS == 0)return false;for(int i = 0;i< lenT;i++){if(t.charAt(i) == s.charAt(p)){p++;}}if(p == lenS)return true;return false;}
}

解法二、动态规划

顺便提前去学了一下动态规划~归纳核心：先求子问题，根据子问题求父问题。保存子问题答案，避免重复运算。

算法-动态规划 Dynamic Programming--从菜鸟到老鸟-CSDN博客

对于f[i][j]，表示t中从i开始，j字符第一次出现的位置。大循环表从后往前遍历，小循环表26个字母遍历，在小循环中，如果位置i是字母j，那么f[i][j]=i，表明i处出现了。否则，是f[i+1][j]，相当于绵延、查表求解，子问题和父问题答案相等。（例如"abcd"，查c之后c的位置，就是2。查b之后c的位置，就是b+1=c那里存的。查a之后c的位置，就是a+1=b（这里已经放进c的答案了）处存的）至于一开始的f[m][i]，可以让m进行转移，代表之后不再存在这个字母。

预处理后，开始考虑n。对于s字符串"abcd",f[0][a]代表0开始后’a‘的位置，如果是m，转移。如果不是，add跳到a的下个位置。+1是因为这个位置已经考虑过了，就是a。

add代表坐标。f之所以有m+1的长度，是为了在m处存下m，也就是维续状态转移。

class Solution {public boolean isSubsequence(String s, String t) {int n = s.length(), m = t.length();int[][] f = new int[m + 1][26];for (int i = 0; i < 26; i++) {f[m][i] = m;}for (int i = m - 1; i >= 0; i--) {for (int j = 0; j < 26; j++) {if (t.charAt(i) == j + 'a')f[i][j] = i;elsef[i][j] = f[i + 1][j];}}int add = 0;for (int i = 0; i < n; i++) {if (f[add][s.charAt(i) - 'a'] == m) {return false;}add = f[add][s.charAt(i) - 'a'] + 1;}return true;}
}作者：力扣官方题解
链接：https://leetcode.cn/problems/is-subsequence/solutions/346539/pan-duan-zi-xu-lie-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

524. 通过删除字母匹配到字典里最长单词（中等）

给你一个字符串 s 和一个字符串数组 dictionary ，找出并返回 dictionary 中最长的字符串，该字符串可以通过删除 s 中的某些字符得到。

如果答案不止一个，返回长度最长且字母序最小的字符串。如果答案不存在，则返回空字符串。

示例 1：
输入：s = "abpcplea", dictionary = ["ale","apple","monkey","plea"]
输出："apple"
示例 2：
输入：s = "abpcplea", dictionary = ["a","b","c"]
输出："a"
提示：

1 <= s.length <= 1000
1 <= dictionary.length <= 1000
1 <= dictionary[i].length <= 1000
s 和 dictionary[i] 仅由小写英文字母组成

解法一、动态规划

上道题学了所以这道题用一下。注意：两个传入参数，这道题和上道题基本算是反的

道理上和上道题差不多~字典序部分讨论，如果len大于最大值，则直接更新；如果等于，那么使用compareTo，返回的是负数则字典序小于，更新。

 public static String findLongestWord(String s, List<String> dictionary) {int lenS = s.length();int[][] f = new int[lenS+1][26];for(int i = 0;i < 26;i++){f[lenS][i] = lenS;}for(int i = lenS - 1;i >= 0;i--){for(int j = 0;j < 26;j++){if(s.charAt(i) == j + 'a'){f[i][j] = i;}else{f[i][j] = f[i+1][j];}}}int maxLen = 0;int index = -1;for(int i = 0;i < dictionary.size();i++){String t = dictionary.get(i);int add = 0;boolean e = true;for(int j = 0;j < t.length();j++){if(f[add][t.charAt(j)-'a'] == lenS){e = false;break;}add = f[add][t.charAt(j)-'a']+1;}if(e && maxLen < t.length()){maxLen = t.length();index = i;}else if(e && maxLen == t.length()){if(dictionary.get(i).compareTo(dictionary.get(index))<0){index = i;}}}if(index == -1)return "";return dictionary.get(index);}

解法二、双指针

同题一解法。这个if判断字典序和长度的方式，比我简明很多（直接记字符串就好）

class Solution {public String findLongestWord(String s, List<String> dictionary) {String res = "";for (String t : dictionary) {int i = 0, j = 0;while (i < t.length() && j < s.length()) {if (t.charAt(i) == s.charAt(j)) {++i;}++j;}if (i == t.length()) {if (t.length() > res.length() || (t.length() == res.length() && t.compareTo(res) < 0)) {res = t;}}}return res;}
}作者：力扣官方题解
链接：https://leetcode.cn/problems/longest-word-in-dictionary-through-deleting/solutions/996014/tong-guo-shan-chu-zi-mu-pi-pei-dao-zi-di-at66/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

解法三、先排序再判断

长的和字典序小的放前面，之后直接遍历返回第一个就好啦。感觉这个写比较器的方法没学过，我学一下···开销肯定更大，因为不符合的部分也排序了

class Solution {public String findLongestWord(String s, List<String> dictionary) {Collections.sort(dictionary, new Comparator<String>() {public int compare(String word1, String word2) {if (word1.length() != word2.length()) {return word2.length() - word1.length();} else {return word1.compareTo(word2);}}});for (String t : dictionary) {int i = 0, j = 0;while (i < t.length() && j < s.length()) {if (t.charAt(i) == s.charAt(j)) {++i;}++j;}if (i == t.length()) {return t;}}return "";}
}作者：力扣官方题解
链接：https://leetcode.cn/problems/longest-word-in-dictionary-through-deleting/solutions/996014/tong-guo-shan-chu-zi-mu-pi-pei-dao-zi-di-at66/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

521. 最长特殊序列 Ⅰ（简单）

给你两个字符串 a 和 b，请返回这两个字符串中 最长的特殊序列 的长度。如果不存在，则返回 -1 。

「最长特殊序列」 定义如下：该序列为 某字符串独有的最长

子序列
（即不能是其他字符串的子序列） 。

字符串 s 的子序列是在从 s 中删除任意数量的字符后可以获得的字符串。

例如，"abc" 是 "aebdc" 的子序列，因为删除 "aebdc" 中斜体加粗的字符可以得到 "abc" 。 "aebdc" 的子序列还包括 "aebdc" 、 "aeb" 和 "" (空字符串)。

示例 1：
输入: a = "aba", b = "cdc"
输出: 3
解释: 最长特殊序列可为 "aba" (或 "cdc")，两者均为自身的子序列且不是对方的子序列。
示例 2：
输入：a = "aaa", b = "bbb"
输出：3
解释: 最长特殊序列是 "aaa" 和 "bbb" 。
示例 3：
输入：a = "aaa", b = "aaa"
输出：-1
解释: 字符串 a 的每个子序列也是字符串 b 的每个子序列。同样，字符串 b 的每个子序列也是字符串 a 的子序列。

解法一、脑筋急转弯简化

一个字符串最长的特殊子序列当然是它自己，如果父序列都不是特殊的，那子序列也一定不是。

class Solution {public int findLUSlength(String a, String b) {int lenA = a.length();int lenB = b.length();if(lenA > lenB){return lenA;}else if(lenA < lenB){return lenB;}else{if(!a.equals(b))return lenA;}return -1;}
}

或者（原来这里可以用三目，学到了）

class Solution {public int findLUSlength(String a, String b) {return !a.equals(b) ? Math.max(a.length(), b.length()) : -1;}
}作者：力扣官方题解
链接：https://leetcode.cn/problems/longest-uncommon-subsequence-i/solutions/1306210/zui-chang-te-shu-xu-lie-i-by-leetcode-so-v9sr/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

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] 只包含小写英文字母

解法一、双指针遍历

双指针即判断一个字符串是否是另一个字符串的子序列的方式。根据521题的讨论可得，子序列是，父序列未必是；父序列是，子序列一定是。也就是说，写成逻辑语言，父序列是=>子序列是

基本逻辑：如果一个字符串不是剩余所有字符串的子序列，那么把它的长度纳入考虑。

但这道题最致命的点，其实在考虑了521之后，会下意识认为它也有方式简化。。。起初用了排序的思想，按照字典序排，从长往短遍历。对于同一长度的字符串组，如果一个字符串不与任何字符串相等，那么它就是答案。该方式简短了isSubseq。

但是太复杂了。。比如：不能圈定固定长度。

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) {if (i != j && isSubseq(strs[i], strs[j])) {check = false;break;}}if (check) {ans = Math.max(ans, strs[i].length());}}return ans;}public boolean isSubseq(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;}return ptS == s.length();}
}作者：力扣官方题解
链接：https://leetcode.cn/problems/longest-uncommon-subsequence-ii/solutions/1623415/zui-chang-te-shu-xu-lie-ii-by-leetcode-s-bo2e/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

解法二参照521的长度简化（失败）

想的是排序然后同长度圈层遍历判断，事实证明根本不可能，因为短的字符串也可以是长的字符串的子序列

但写了很久，所以还是放一下

class Solution {public static int findLUSlength(String[] strs) {Arrays.sort(strs, new Comparator<String>() {@Overridepublic int compare(String s1, String s2) {return Integer.compare(s1.length(), s2.length());}});int len = strs.length;int ans = -1;int p = len - 2,q = len - 1;while(p >= 0){while(p > 0 && strs[p].length() == strs[q].length()){p--;}if(strs[p].length()!= strs[q].length())p++;boolean check = true;for(int j = p;j < q;j++){for(int h = p;h<q;h++){if(j != h && strs[j].equals(strs[h])){check = false;break;}}if(check)ans = Math.max(ans,strs[j].length());}if(ans != -1)return ans;p = p-2;q = p+1;}if(strs[0].length() != strs[1].length())return strs[0].length();return -1;}
}