Leetcode 522. 最长特殊序列 II （判断子序列优化）

本文主要是介绍Leetcode 522. 最长特殊序列 II （判断子序列优化），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Leetcode 522. 最长特殊序列 II

暴力枚举

根据特殊序列的定义，枚举出每个 strs[ i ] 的所有子序列，再将这个子序列与strs中的其他串比较判断
使用二进制位运算枚举一个str的所有子序列
使用双指针指向两个串的开头，同时移动判断是否是子序列

子串定义为原字符串中任意连续的一段，
如"abcd"中的“bc”
子序列 定义为原字符串中选择某些字符所组成的新字符串，它们的相对顺序不变，不需连续
如“abcd”中的“ac”

class Solution {// 判断函数  s是否为t的子序列public boolean isSubsequence(String s, String t) {int m = s.length();int n = t.length();int ls = 0;int lt = 0;while(ls < m && lt < n){if(s.charAt(ls) == t.charAt(lt)){ls ++;}lt ++;}return ls == m;}public int findLUSlength(String[] strs) {int n = strs.length;int res = -1;for(int i = 0 ; i < n; i ++){String s = strs[i];int len = s.length();// 枚举s的每个子序列for(int k = 1; k < (1 << len); k ++){StringBuffer sb = new StringBuffer("");for(int j = 0; j < len; j ++){if((k & (1 << j)) != 0){ // 不能写成 k & (1 << j)) == 1，与运算后的1可能不在末位sb.append(s.charAt(j));}}// 获得子序列ssString ss = sb.toString();boolean flag = true;for(int p = 0; p < n; p ++){if(p != i && isSubsequence(ss, strs[p])){flag = false;break;}}if(flag)res = Math.max(res, ss.length());}}return res;}
}

优化

注意到，如果一个str的子序列满足条件“不是其他字符串的子序列”，那个这个子序列无论如何扩充，扩充后的子序列也必定不是其他字符串的子序列
如子序列“abc”不是“qwerty”、“asdfgh”、“zxcvbn”的子序列，那么将“abc”任意扩充为“axbycz”，也必定不是其他字符串的子序列
由此推出，若str的一个子序列满足条件，那么str本身也必定满足条件

由此问题转化为，判断str[ i ]是否是其他strs的子序列，找出最长的一个str[ i ]返回长度

class Solution {public boolean isSubsequence(String s, String t) {int m = s.length();int n = t.length();int ls = 0;int lt = 0;while(ls < m && lt < n){if(s.charAt(ls) == t.charAt(lt)){ls ++;}lt ++;}return ls == m;}public int findLUSlength(String[] strs) {int n = strs.length;int ans = -1;for(int i = 0; i < n ; i++){String s = strs[i];// 避免计算更小的答案int len = s.length();if(len <= ans)continue;boolean flag = true;for(int j = 0; j < n; j ++){if(i != j && isSubsequence(s, strs[j])){flag = false;break;}}if(flag)ans = Math.max(ans, s.length());}return ans;}
}