动态规划算法,计算单词距离代码,Python代码库,德仔网

代码语言

代码分类

【Python】动态规划算法,计算单词距离

作者:dezai / 发布于2014/9/11/ 616


	#!/usr/bin/env python
	#coding=utf-8

	def word_distance(m,n):
	 """compute the least steps number to convert m to n by insert , delete , replace .
	 动态规划算法,计算单词距离
	 >>> print word_distance("abc","abec")
	 1
	 >>> print word_distance("ababec","abc")
	 3
	 """
	 len_1=lambda x:len(x)+1

	 c=[[i] for i in range(0,len_1(m)) ]
	 c[0]=[j for j in range(0,len_1(n))]

	 for i in range(0,len(m)):
	 # print i,' ',
	 for j in range(0,len(n)):
	 c[i+1].append(
	 min(
	 c[i][j+1]+1,#插入n[j]
	 c[i+1][j]+1,#删除m[j]
	 c[i][j] + (0 if m[i]==n[j] else 1 )#改
	 )
	 )
	 # print c[i+1][j+1],m[i],n[j],' ',
	 # print ''
	 return c[-1][-1]

	import doctest
	doctest.testmod()
	raw_input("Success!")

评论列表

本站所提供的代码，版权归原作者所有，若有侵犯作者版权，请与我们联系，我们将立即删除或修改。谢谢!
本站所有代码发布及提供者。

试试其它关键字

　动态规划　

同语言下

可能有用的

dezai贡献的其它代码(1065)