解题思路:
动态规划。
①创建一个大小为(n+1)*(m+1)的二维数组,命名为dp,n和m分别为字符串s、t的长度。
其中dp[i][j]表示s中的前i个字符要想包含t的前j个字符最少需要修改几次。
②dp[i][0] = 0(i = 0 to n)
③状态转移方程
当s[i] = t[j]时,这时我们不用进行变换则,dp[i][j] = dp[i-1][j-1]
当s[i] != t[j]时,这时有两种情况,一种情况是,在s中没取到第i个字符时,已经可以包含t取到字符j了。
另一种情况是,此时t取到第j个字符时还未被包含,那么在此时,就要进行一次变换
所以dp[i][j] = min(dp[i-1][j],dp[i-1][j-1]+1)
注意事项:
参考代码:
from cmath import inf s = input().strip() t = input().strip() n = len(s) m = len(t) dp = [[inf for j in range(m+1)] for i in range(n+1)] for i in range(n+1): dp[i][0] = 0 for i in range(1,n+1): for j in range(1,m+1): if s[i-1] == t[j-1]: dp[i][j] = dp[i-1][j-1] else: dp[i][j] = min(dp[i-1][j],dp[i-1][j-1]+1) print(dp[n][m])
0.0分
6 人评分
C语言考试练习题_保留字母 (C语言代码)浏览:700 |
2003年秋浙江省计算机等级考试二级C 编程题(1) (C语言代码)浏览:516 |
GC的苦恼 (C语言代码)浏览:621 |
永远的丰碑 (C语言代码)浏览:518 |
分糖果 (C语言代码)浏览:914 |
时间转换 (C语言代码)浏览:627 |
C语言程序设计教程(第三版)课后习题10.7 (用指针求解)浏览:1474 |
C语言程序设计教程(第三版)课后习题8.1 (C语言代码)浏览:565 |
C语言程序设计教程(第三版)课后习题8.5 (C语言代码)浏览:662 |
printf基础练习 (C语言代码)浏览:1797 |