已知两个字符串s与t, 要研究如何把字符串s经由一连串编修动作变成t。能够使用的就是插入一个符号, 以及删除一个符号; 把某个符号换成另一个, 就可以通过先把它删除再在原地插入所需的符号来完成。编写一个程序, 接收s与t, 找出如何才能够在最少步骤之下把s改成t。

说明: 把一个字符串修改成第一个字符串在语汇分析(Lexical Analysis)与拼字分析(Spelling Check)中有很重要的地位。例如, 已知s这个字符串可能有问题, 而在s中应该会出现t[1],t[2]…t[k], 这几个字符串其中之一, 但是用哪一个比较好呢? 通常会选使用最少修动而能够把s改出来的那一个, 这一项技巧在化学中研究分子结构相当有用.

如果已知ABCD这个字符串,想把它改成XBYD,一看就知道可以把A换成X, C成Y就行了, 这就有了4个动作一删除A, 插入X, 删除C, 插入Y; 但也可以把ABCD全部删除,再插入XBYD, 这就要8个动作, 4个删除, 4个插入。当然, 两者相比, 自然是第一个方法好些。这是一个简单的例子, 但当s与t这两个字符串很长时就不那么容易看出结果了, 因此这个题目就是要求编写这样的一个程序.

前面的最长部分序列(Longest Common Sequence)的技巧对本题非常有帮助, 不妨先看看LCS这个程序

a[1]a[2]…a[i]与b[1]b[2]…b[j]相互变换可以分为以下几种情况

1. 如果a[i] = b[j], 于是a[1][2]…a[i]变成b[1]b[2]…b[j]的次数等于a[1]a[2]…a[i-1]变成b[1]b[2]…b[j-1]的次数
2. 如果a[i] != b[j], 分成三种情况讨论: 第一, 检查a[1]a[2]…a[i]变成b[1]…b[j-1]后，再插入一个b[j]; 第二, 检查a[1]…a[i-1]变成b[1]b[2]…b[j]后再插入一个a[i]; 第三: a[1]…a[i-1]变成b[1]b[2]…b[j-1]后，删除a[i], 插入b[j]

解答见string_edit.py