2007-11-04

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


#!/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!")
评论
发表评论

提醒: 该博客已发表在公共论坛，博客所有留言会成为论坛回贴，留言请注意遵守论坛发贴规则

您还没有登录，请登录后发表评论