酒店网站搜索引擎优化方案,深圳seo网站排名优化,注册个公司要多少钱费用,湖南有实力seo优化写得好的解题思路链接#xff1a;url1 url2(动态规划写的比较好)
输入#xff1a;两个字符串s和t#xff0c;t可能会很长 输出#xff1a;s是否是t的子序列。 规则#xff1a;字符串子序列的定义是#xff1a;通过删除字符串t的部分字符但是不能改变字符相对位置#x…写得好的解题思路链接url1 url2(动态规划写的比较好)
输入两个字符串s和tt可能会很长 输出s是否是t的子序列。 规则字符串子序列的定义是通过删除字符串t的部分字符但是不能改变字符相对位置能够得到字符串s则s是t的一个子序列。 直观分析就是挨个判断s中的字符串是否在t中出现。要求出现位置是递增的。 public boolean isSubsequenceV3(String s, String t) {if(snull || s.length()0) return true;int m s.length();int n t.length();int index 0;for(int i0;in;i){if(t.charAt(i) s.charAt(index)){index;if(index m) {return true;}}}return false;}动态规划思路先做暴力搜索。t需要删除部分字符成为s。当t[i]s[i]的时候可以选择使用t[i]或者不使用t[i]。 public boolean isSubsequence(String s, String t) {this.s s;this.t t;return f(0,0);}private boolean f(int i,int j){if(i s.length()){return true;}if(j t.length()){return false;}if(s.charAt(i) t.charAt(j)){if(f(i1,j1)) return true;}return f(i,j1);}设置数组dp[i][j]dp[i][j]true表示子串s[0,i]是子串t[0,j]的一个子序列。
dp[i][j] dp[i-1][j-1] 如果s[i]t[j]。 dp[i][j] dp[i][j-1] 如果s[i]!t[j]。 public boolean isSubsequenceV2(String s, String t) {if(snull || s.length()0) return true;if(tnull || t.length()0) return false;boolean[][] dp new boolean[s.length()][t.length()];int m s.length();int n t.length();for(int j 0;j n;j){if(s.charAt(0) t.charAt(j)){dp[0][j] true;}else{dp[0][j] (j0?dp[0][j-1]:false);}}for(int i1;im;i){for(int j0;jn;j){if(s.charAt(i) t.charAt(j)){dp[i][j] (j0?dp[i-1][j-1]:false);}else{dp[i][j] j0? dp[i][j-1] :false;}}}return dp[m-1][n-1];}当然空间还可以进一步优化
