一次编辑
字符串有三种编辑操作:插入一个字符、删除一个字符或者替换一个字符。 给定两个字符串,
编写一个函数判定它们是否只需要一次(或者零次)编辑。
示例 1:
输入:
first = "pale"
second = "ple"
输出: True
示例 2:
输入:
first = "pales"
second = "pal"
输出: False
class Solution:
def oneEditAway(self, first: str, second: str) -> bool:
lenfirst=len(first)
lensecond=len(second)
if abs(lenfirst-lensecond)>1:
return False
dp = [[0] * (lensecond+1) for _ in range(lenfirst+1)]
for i in range(0,lenfirst+1):
dp[i][0]=i
for j in range(0,lensecond+1):
dp[0][j]=j
for i in range(1,lenfirst+1):
for j in range(1,lensecond+1):
if first[i-1]==second[j-1]:
dp[i][j]=dp[i-1][j-1]
else:
dp[i][j]=min(dp[i-1][j],min(dp[i-1][j-1],dp[i][j-1]))+1
return dp[lenfirst][lensecond]<=1
评论0