package dp.isSubsequence; /** * 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 * 两个字符串都只由小写字符组成。 */ public class isSubsequence { //最长子序列问题 public static boolean isSubsequence(String s, String t) { if (s == ""||s.length()==0) { return true; } char[] char1 = s.toCharArray(); char[] char2 = t.toCharArray(); int len1 = s.length(); int len2 = t.length(); int[][] dp = new int[len1 + 1][len2 + 1]; for (int i = 1; i <= len1; i++) { for (int j = 1; j <= len2; j++) { if (char1[i - 1] == char2[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + 1; } else { dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); } if (dp[i][j] == len1) { return true; } } } return false; } public static void main(String[] args) { String s = ""; String t = "ahbgdc"; System.out.println(isSubsequence(s, t)); } }
不会,我可以学;落后,我可以追赶;跌倒,我可以站起来!