计算字符串距离

一、原理介绍

    原理摘自<<编程之美>>，计算两个字符串s和t的距离，首先看s的第一个字符和t的第一个字符是否相等，
如果相等则计算s[2...n]和t[2...n]的距离，如果不相等则经过一步操作之后，再比较s[2...n]与t[1...n]或者
s[1...n]与t[2...n]或者s[2...n]与t[2...n]的距离。

二、实现

1.首先看一下递归的实现(此处用python来实现)：
    def calculate_string_distance(s,s_begin,s_end,t,t_begin,t_end):
		if s_begin>s_end:
			if t_begin>t_end:
				return 0
			else:
				return t_end-t_begin+1
		if t_begin>t_end:
			if s_begin>s_end:
				return 0
			else:
				return s_end-s_begin+1
		if s[s_begin]==t[t_begin]:
			return calculate_string_distance(s,s_begin+1,s_end,t,t_begin+1,t_end)
		else:
			d1=calculate_string_distance(s,s_begin+1,s_end,t,t_begin,t_end)
			d2=calculate_string_distance(s,s_begin,s_end,t,t_begin+1,t_end)
			d3=calculate_string_distance(s,s_begin+1,s_end,t,t_begin+1,t_end)
			return min(d1,d2,d3)+1
	递归有两个问题：a.如果递归的深度太大的话会导致栈溢出，b.重复计算
			
2.动态规划的实现：
  def calculate_string_distance2(s,t):
	record=[[0 for j in range(len(t)+1)] for i in range(len(s)+1)]
	for j in range(len(t)+1):
		record[0][j]=j
	for i in range(len(s)+1):
		record[i][0]=i
	for i in range(1,len(s)+1):
		for j in range(1,len(t)+1):
			d1=record[i-1][j-1]+(0 if s[i-1]==t[j-1] else 1)
			d2=record[i-1][j]+1
			d3=record[i][j-1]+1
			record[i][j]=min(d1,d2,d3)
	return record[len(s)][len(t)]