如何计算编辑距离:

1.两字字串都为空，编辑距离为0

2.当其中一个为空时，编辑距离为另外一个字串的长度。

3.当两个字串非空时（长度分别为i 和 j时），取下面3种情况最小值：

3.1 当i-1 和 j的编辑距离已知时，直接+1 为 i和j的编辑距离

3.2 当i 和 j-1的编辑距离已知时，直接+1 为 i和j的编辑距离

3.3 当i-1 和 j-1的编辑距离已知时，如果i-1字符和j-1字符相等则+0，如果不相等则+1为 i和j的编辑距离。

应该用动态规划：

int dp[m+1][n+1] //定义长度为i的字串和长度为j的字串之间的编辑距离

两个字符串最前面插入一个空字符，初始化[i][0] base case 为i，初始化[0][j] base case 为j；

编写状态转移方程

def editDistance(str1, str2):
len1, len2 = len(str1) + 1, len(str2) + 1
dp = [[0 for i in range(len2)] for j in range(len1)]#创建存放编辑距离的二维矩阵len1*len2
for i in range(len1):
dp[i][0] = i
for j in range(len2):
dp[0][j] = j
for i in range(1, len1):
for j in range(1, len2):
dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + (str1[i - 1] != str2[j - 1]))
return dp[-1][-1]

while True:
try:
str1=input()
str2=input()
if str1=='' or str2=='':
print(max(len(str1), len(str2)))#当其中一个为空时，编辑距离为另外一个字串的长度
else:
print(editDistance(str1, str2))
except:
break