Python基于动态规划算法计算单词距离

本文实例讲述了Python基于动态规划算法计算单词距离。分享给大家供大家参考。具体如下：

    #!/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!")

希望本文所述对大家的Python程序设计有所帮助。