crm网站下载,江苏常州建设局网站,黑龙江期刊网站制作,常州网站排名优化题意理解#xff1a; 给定字符串 s 和 t #xff0c;判断 s 是否为 t 的子序列。 字符串的一个子序列是原始字符串删除一些#xff08;也可以不删除#xff09;字符而不改变剩余字符相对位置形成的新字符串。#xff08;例如#xff0c;ace是abcde 给定字符串 s 和 t 判断 s 是否为 t 的子序列。 字符串的一个子序列是原始字符串删除一些也可以不删除字符而不改变剩余字符相对位置形成的新字符串。例如ace是abcde的一个子序列而aec不是。 即判断s和t是否存在一个最长公共子序列且该最长公共子序列s 这里采用一个动态规划的思路求解最长公共子序列其长度s.size 解题思路 (1) 定义dp数组 定义二维dp数组dp[i][j]表示s第i个元素前t第j个元素前最长公共子序列。 ij指示的是元素之间的位置 其i属于[0,s.size1], j属于[0,t.size1] 2初始化 dp[0][j]和dp[i][0]表示第一行第一列其都是用一个空数组和一个非空数组求其最长公共给子序列所以全部初始化为0. 其余元素初始化为0后续操作会被覆盖掉。 3递推公式 if(s[i-1]t[j-1]) dp[i][j]dp[i-1][j-1]1 else dp[i][j]max(dp[i][j-1]dp[i-1][j]) (4)返回 if(dp[s.size-1][t.size-1]s.size) return true; else return false; 1.动态规划
public boolean isSubsequence(String s, String t) {int[][] dpnew int[s.length()1][t.length()1];for(int i0;is.length();i){Arrays.fill(dp[i],0);}for(int i1;is.length();i){for(int j1;jt.length();j){if(s.charAt(i-1)t.charAt(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[s.length()][t.length()]s.length()) return true;return false;}
2.分析 时间复杂度O(n^2) 空间复杂度O(n^2)
