Python：每日一题 376

kinkon

1. def f376(word1, word2):
   
2.    
   
3.     n1, n2 = len(word1), len(word2)
   
4.     dp = [0] * (n2 + 1)
   
5.     for i in range(n1 + 1):
   
6.         temp = [0] * (n2 + 1)
   
7.         for j in range(n2 + 1):
   
8.             if i == 0 or j == 0:
   
9.                 temp[j] = i + j
   
10.             elif word1[i - 1] == word2[j - 1]:
    
11.                 temp[j] = dp[j - 1]
    
12.             else:
    
13.                 temp[j] = min(dp[j], temp[j - 1]) + 1
    
14.         dp = temp[:]
    
15.         #print(dp)
    
16. 
    
17.     return dp[n2]

复制代码

kinkon

@zltzlt 想问一下两个字符串是不是一样长？

kinkon

蒋博文 发表于 2020-4-15 14:57
应该是可以不一样长的吧。反正我这样写的。

嗯嗯，我也是这样想的，字符串一样长的话会简单些

kinkon

这时间差得有点多啊，看来优化空间很大