手机网站 备案,电子政务门户网站建设代码,制作微信网页,手机网站建设讯息给你两个字符串 s 和 t #xff0c;统计并返回在 s 的 子序列 中 t 出现的个数。
题目数据保证答案符合 32 位带符号整数范围。
思路一#xff1a;动态规划
int numDistinct(char * s, char * t){int len1strlen(s),len2strlen(t);uint64_t dp[len11][len21];memset(dp,0,…给你两个字符串 s 和 t 统计并返回在 s 的 子序列 中 t 出现的个数。
题目数据保证答案符合 32 位带符号整数范围。
思路一动态规划
int numDistinct(char * s, char * t){int len1strlen(s),len2strlen(t);uint64_t dp[len11][len21];memset(dp,0,sizeof dp);for(int i0;ilen1;i)dp[i][0]1;for(int i1;ilen1;i){for(int j1;jlen2;j){ if(s[i-1]!t[j-1])dp[i][j]dp[i-1][j];elsedp[i][j]dp[i-1][j-1]dp[i-1][j];}}if(dp[len1][len2]INT_MAX)return -1;return dp[len1][len2];
}
分析
本题要计算t在s子序列的个数可想到使用动态规划的方法根据两个字符串的顺序不断向后匹配当匹配的相同位置字符不相同时调用前面匹配成功的dp[i-1][j]当字符相同时dp[i][j]dp[i-1][j-1]dp[i-1][j]最后判断是否大于int范围返回dp[len1][len2];
总结
本题考察动态规划在字符串之中的应用考虑每一位匹配的结果调用前一位的结果即可解决
