计算字符串的编辑距离和单向链表中倒数第k个结点

含义：给定两个字符串，将一个字符串转换成另一个字符串所需要的最少单字符编辑操作（插入、删除、替换）次数。例如 abcdefg 与 abcdef 只需要一次操作就可使得两个字符串一样，即要么第一个字符串删除字符 g，要么第二个字符串增加字符 g。

利用动态规划来解决这道题。假设有两个字符串 aStr = "appa" 和 bStr = "apple"，其字符串的长度分别为 aLen 和 bLen，而 $i\in [0,aLen]$，而 $j\in [0,bLen]$。

• DP 表定义：dp[i][j] 表示 aStr 的前 i 个字符（即 aStr[0..i-1]）转换为 bStr 的前 j 个字符（即 aStr[0..j-1]）的最小编辑次数。

特殊地，dp[0][j] = j 表示 aStr = "" 转换为 bStr[0..j-1] 需要 j 次插入；
dp[i][0] 表示将 aStr[0..i-1] 转换为空字符串 “” 需要 i 次删除。

• 递推关系的构建：
  • 当 aStr[i-1] 与 b[j-1] 相等时，则不需要进行任何操作，即 dp[i][j] = dp[i-1][j-1]；
  • 当 aStr[i-1] 与 b[j-1] 不相等时，需要从三个不同的操作中选择总操作数最小的编辑次数，并修改 dp[i][j]：
    • 删除：删除 aStr[i-1] 后 aStr[0..i-2] 与 bStr[0..j-1] 相匹配，所以 dp[i][j] = dp[i-1][j] + 1;
    • 增加：在 aStr 的第 i-1 个后增加一个字符 aStr[j-1]，且 aStr[0..i-1] 与 bStr[0..j-2] 相匹配，所以 dp[i][j] = dp[i][j-1] + 1;
    • 替换：将 aStr[i-1] 替换为 bStr[j-1]，且 aStr[0..i-2] 与 bStr[0..j-2] 相匹配，所以 dp[i][j] = dp[i-1][j-1] + 1；
  • 最终取得最小值：dp[i][j]=min(dp[i][j−1]+1, dp[i−1][j]+1, dp[i−1][j−1]+1) 。
    

# 1. 从控制台获取两个字符串
aStr = input()
bStr = input()# 2. 构建 DP 表，并特殊处理第一行和第一列
dp = [[j for j in range(len(bStr) + 1)] for _ in range(len(aStr) + 1)]
for i in range(1, len(aStr) + 1):dp[i][0] = dp[i-1][0] + 1# 3. 更新 DP 表 
for i in range(1, len(aStr) + 1):for j in range(1, len(bStr) + 1):if aStr[i-1] == bStr[j-1]:dp[i][j] = dp[i-1][j-1]else:add = dp[i][j-1] + 1delelte = dp[i-1][j] + 1replace = dp[i-1][j-1] + 1dp[i][j] = min(add, delelte, replace)print(dp[len(aStr)][len(bStr)])

def printLastK(n, vals, k):# i = 0, j = k；然后一起前进；# 当 j == n 时，vals[i] 就是倒数 K 个结点i = 0j = kwhile j < n:i += 1j += 1print(vals[i])while True:try:n = int(input())vals = list(map(int, input().split(' ')))k = int(input())# print(n, vals, k)printLastK(n, vals, k)except:break