Python基于动态规划算法计算单词距离
作者:Sephiroth 发布时间:2021-09-18 11:18:16
标签: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程序设计有所帮助。
0
投稿
猜你喜欢
- 运行效果:完整代码from tkinter import *def click(num): global op op
- 前言help(argparse)查看说明文档,“argparse - Command-line parsing libr
- loss函数如何接受输入值keras封装的比较厉害,官网给的例子写的云里雾里,在stackoverflow找到了答案You can wrap
- 代码如下:title=request("title") title=replace(title,"chr(3
- 将字符串字段转为数字排序或比大小mysql里面有个坑就是,有时按照某个字段的大小排序(或是比大小)发现排序有点错乱。后来才发现,是我们想当然
- 由于最近测试需要录制系统界面的操作过程,因为都是全屏的操作,所以用python做一个简单的录屏小工具。实现过程也是比较简单,就是通过对屏幕操
- 最近为了做Hyperledger Fabric国密改造,涉及到了golang源码的改动。特将操作过程整理如下,以供参考:golang的源码安
- python openvc 裁剪图片下面是4个坐标代码:import cv2#裁剪图片路径input_path,四个裁剪坐标为:y1,y2,
- SQL2005安装安装步骤安装Microsoft SQL Server 2005 数据库步骤:第一步:将Microsoft SQL Serv
- 1.初始化(使用session前都要使用,一个页面用一个就可以了)session_start();2.保存$_SESSION[$sessio
- 用tornado web服务的基本流程1.实现处理请求的Handler,该类继承自tornado.web.RequestHandler,实现
- 如下所示:depot_name = models.CharField( u'设备库房名称', bla
- strConnString = "driver={MySQL ODBC 3.51 
- 背景在业务数据统计分析中基本都会涉及到各省区的分析,数据可视化是数据分析的一把利器,这些省区的数据一般会用地图可视化出来,这样一些规律可以被
- 描述安装python库有时会遇到安装失败的情况。这让我很难受,下面是一种解决办法供大家参考,我们可以换一种方法安装,比如从官网下载来安装。下
- 在Bootstrap的官网上,提供了一种导航栏的组件:只要在站点文件夹放好JQ与Bootstrap输入如下代码: <!DOCTYPE
- --创建测试表 DECLARE @Users TABLE ( ID INT IDENTITY(1,1), UserInfo XML ) --
- 枚举类Enum枚举类,在企业开发中用的比较多当我们需要定义常量时,一个办法是用大写的变量通过整数来定义,例如月份:# 当项目中需要使用12个
- 今天在研究Plotly绘制散点图的方法,供大家参考,具体内容如下使用Python3.6 + PlotlyPlotly版本2.0.0在开始之前
- console.log,作为一个前端开发者,可能每天都会用它来分析调试,但这个简单函数背后不简单那一面,你未必知道……基础首先,简单科普这个