给定两个字符串 str1 和 str2 ,请你算出将 str1 转为 str2 的最少操作数。
你可以对字符串进行3种操作:
1.插入一个字符
2.删除一个字符
3.修改一个字符。
字符串长度满足 ,保证字符串中只出现小写英文字母。
"nowcoder","new"
6
"nowcoder"=>"newcoder"(将'o'替换为'e'),修改操作1次 "nowcoder"=>"new"(删除"coder"),删除操作5次
"intention","execution"
5
一种方案为: 因为2个长度都是9,后面的4个后缀的长度都为"tion",于是从"inten"到"execu"逐个修改即可
"now","nowcoder"
5
class Solution: def editDistance(self , s1: str, s2: str) -> int: # write code here n1=len(s1) n2=len(s2) #dp[i+1][j+1]为s1[0..i]到s2[0...j]的最少操作数 dp = [[0]*(n2+1) for _ in range(n1+1)] #确定初始值 for j in range(n2+1): dp[0][j]=j for i in range(n1+1): dp[i][0]=i #状态转移 for i in range(1,n1+1): for j in range(1,n2+1): if s1[i-1]==s2[j-1]: dp[i][j]=dp[i-1][j-1] else: #[i][j],由于i和j-1匹配,i处插得到新的i,至j匹配 #[i][j],由于i-1和j匹配,i处删,至i-1匹配 #替换,由于i-1和j-1匹配,i处替换成j dp[i][j] = min(dp[i][j-1]+1, \ dp[i-1][j]+1, \ dp[i-1][j-1]+1) return dp[n1][n2]
# # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param str1 string字符串 # @param str2 string字符串 # @return int整型 # class Solution: def editDistance(self , str1: str, str2: str) -> int: # write code here m=len(str1) n=len(str2) dp=[[0]*(n+1) for i in range(m+1)] #第一行 for i in range(n+1): dp[0][i]=i #第一列 for i in range(m+1): dp[i][0]=i for i in range(1, m+1): for j in range(1,n+1): if str1[i-1]==str2[j-1]: dp[i][j]=dp[i-1][j-1] else: #可以是删除,添加,修改 #替换dp[i-1][j-1] 删除dp[i-1][j] 添加dp[i][j-1] dp[i][j]=min(min(dp[i][j-1],dp[i-1][j]),dp[i-1][j-1])+1 print(dp) return dp[m][n]
class Solution: def editDistance(self , str1: str, str2: str) -> int: # write code here n = len(str1) m = len(str2) # n+1行 m+1列 [0][0]为空字符 dp = [[0 for j in range(m+1)] for i in range(n+1)] # 第一行: 空字符转化为 str2 所需最少操作数 for j in range(m+1): dp[0][j] = j # 第一列: str1转化为 空字符 所需最少操作数 for i in range(n+1): dp[i][0] = i for i in range(1, n+1): for j in range(1, m+1): # dp[i][j]:将str1[:i]全部修改为str2[:j]所需最小操作数(右闭) if str1[i-1] == str2[j-1]: dp[i][j] = dp[i-1][j-1] else: # 插入:先完成调整使str1[:i]=str2[:j-1],str1末尾再插入str2[j] insert = dp[i][j-1] + 1 # 删除:先完成调整使str1[:i-1]=str2[:j],再删除str1[i] remove = dp[i-1][j] + 1 # 修改:先完成调整使str1[:i-1]=str2[:j-1],再修改str1[i]=str2[j] change = dp[i-1][j-1] + 1 dp[i][j] = min(insert, remove, change) return dp[-1][-1]
经典动态规划
先把s1=[]和s2=[]的边界位置先填充,再填充中间位置
时间复杂度:O(mn) 空间复杂度:O(mn)
class Solution: def editDistance(self , str1: str, str2: str) -> int: n = len(str1) m = len(str2) dp = [[0]*(m+1) for i in range(n+1)] for i in range(1, n+1): dp[i][0] = dp[i-1][0] + 1 for j in range(1, m+1): dp[0][j] = dp[0][j-1] + 1 for i in range(1, n+1): for j in range(1, m+1): if str1[i-1] == str2[j-1]: dp[i][j] = dp[i-1][j-1] else: dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1 return dp[n][m]
class Solution: def editDistance(self , str1: str, str2: str) -> int: # write code here if not str1: return len(str2) if not str2: return len(str1) dp = [[0 for i in range(len(str2)+1)] for j in range(len(str1)+1)] for i in range(1,len(str1)+1): dp[i][0] = i for j in range(1,len(str2)+1): dp[0][j] = j for i in range(1,len(str1)+1): for j in range(1,len(str2)+1): if str1[i-1]==str2[j-1]: dp[i][j] = dp[i-1][j-1] else: dp[i][j] = min(dp[i-1][j-1],min(dp[i-1][j],dp[i][j-1]))+1#改,删,增 return dp[len(str1)][len(str2)]
class Solution: def editDistance(self , str1: str, str2: str) -> int: # write code here m,n =len(str1),len(str2) dp = [[0]*(n+1) for _ in range(m+1)] #初始化,预留空串 for i in range(m+1): dp[i][0] = i for j in range(n+1): dp[0][j] = j for i in range(1,m+1): for j in range(1,n+1): if str1[i-1]!=str2[j-1]: dp[i][j] = min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1 else: dp[i][j] = dp[i-1][j-1] return dp[m][n]