咨询网站模板,wordpress php缓存,jsp做的求职招聘网站百度云,长沙百度公司地址Day 55
392.判断子序列
dp[i][j] 表示以下标i-1为结尾的字符串s#xff0c;和以下标j-1为结尾的字符串t#xff0c;相同子序列的长度为dp[i][j]。
if (s[i - 1] t[j - 1]) t中找到了一个字符在s中也出现了 if (s[i - 1] ! t[j - 1]) 相当于t要删除元素#xff0c;继续匹…Day 55
392.判断子序列
dp[i][j] 表示以下标i-1为结尾的字符串s和以下标j-1为结尾的字符串t相同子序列的长度为dp[i][j]。
if (s[i - 1] t[j - 1]) t中找到了一个字符在s中也出现了 if (s[i - 1] ! t[j - 1]) 相当于t要删除元素继续匹配
if (s[i - 1] t[j - 1])那么dp[i][j] dp[i - 1][j - 1] 1;因为找到了一个相同的字符相同子序列长度自然要在dp[i-1][j-1]的基础上加1
if (s[i - 1] ! t[j - 1])此时相当于t要删除元素t如果把当前元素t[j - 1]删除那么dp[i][j] 的数值就是 看s[i - 1]与 t[j - 2]的比较结果了即dp[i][j] dp[i][j - 1];
class Solution:def isSubsequence(self, s: str, t: str) - bool:dp [[0]*(len(t)1) for _ in range((len(s) 1))]for i in range(1, len(s) 1):for j in range(1, len(t) 1):if s[i-1] t[j-1]:dp[i][j] dp[i-1][j-1] 1else:dp[i][j] dp[i][j-1]if dp[-1][-1] len(s):return Truereturn False class Solution {public boolean isSubsequence(String s, String t) {int length1 s.length(); int length2 t.length();int[][] dp new int[length11][length21];for(int i 1; i length1; i){for(int j 1; j length2; j){if(s.charAt(i-1) t.charAt(j-1)){dp[i][j] dp[i-1][j-1] 1;}else{dp[i][j] dp[i][j-1];}}}if(dp[length1][length2] length1){return true;}else{return false;}}
}115.不同的子序列
dp[i][j]以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]
dp[i][0] 表示以i-1为结尾的s可以随便删除元素出现空字符串的个数。
class Solution:def numDistinct(self, s: str, t: str) - int:dp [[0] * (len(t)1) for _ in range(len(s)1)]for i in range(len(s)):dp[i][0] 1for j in range(1, len(t)):dp[0][j] 0for i in range(1, len(s)1):for j in range(1, len(t)1):if s[i-1] t[j-1]:dp[i][j] dp[i-1][j-1] dp[i-1][j]else:dp[i][j] dp[i-1][j]return dp[-1][-1]
