[LeetCode]题解(python):072-Edit Distance
2024-10-13 12:12:58
题目来源:
https://leetcode.com/problems/edit-distance/
题意分析:
word1最少通过多少步可以变成word2。word1只能进行一下的操作。a)插入一个字符,b)删除一个字符,c)替代一个字符。比如“aba”变成“abc”只需要通过替代最后一个字符就可以达到。
题目思路:
这很明显是一个动态规划的问题。建立一个二维数组ans,其中ans[i][j]代表word1[i:]要变成word2[j:]至少需要多少步。那么如果word1[i] == word2[j],则ans[i][j] = ans[i+1][j+1],否者,ans[i][j]= min(ans[i +1][j],ans[ans[i][j+1],ans[i+1][j+1])/分别代表每个操作/ + 1。只要处理好初始化问题就可以了。
代码(Python):
class Solution(object):
def minDistance(self, word1, word2):
"""
:type word1: str
:type word2: str
:rtype: int
"""
m,n = len(word1),len(word2)
ans = [[0 for i in range(n + 1)] for j in range(m + 1)]
for i in range(m + 1):
ans[i][n] = m - i
for i in range(n + 1):
ans[m][i] = n - i
m -= 1;n -= 1
while m >= 0:
t = n
while t >= 0:
if word1[m] == word2[t]:
ans[m][t] = ans[m + 1][t + 1]
else:
ans[m][t] = min(ans[m][t+1],ans[m+1][t],ans[m+1][t+1]) + 1
t -= 1
m -= 1
return ans[0][0]
转载请注明出处:http://www.cnblogs.com/chruny/p/5069714.html
最新文章
- tshark过滤并保存包特定字段
- 父容器的flowover:hidden 必须配合父容器的宽高height width才能生效
- PHP基于SOAP实现webservice
- jquery-cookie插件怎么读写json数据
- linux 新增挂载新硬盘
- linux 禁止指定账号ssh登陆
- wpf 计算器布局练习
- Javascript UserAgent 获取平台及浏览器信息
- find the safest road--hdu1596
- JQuery标签去重与数组去重
- windows下Visual Studio Code 1.9安装
- js Web存储方式
- Node-debug方法
- ORACLE 多表关联 UPDATE 语句
- django - 总结 - 用户认证组件
- 【Jquery Mobile教程】【问题】- 在页面切换时会闪烁
- C++版 - 剑指offer 面试题24:二叉搜索树BST的后序遍历序列(的判断) 题解
- vue自定义一个v-model
- python 小程序,替换文件中的字符串
- MVC ---- EF高级增删改