Python：每日一题 376

zltzlt

今天的题目：

给定两个字符串 word1 和 word2，找到使得 word1 和 word2 相同所需的最小操作数，每一个操作可以删除任意一个字符串中的一个字符。

示例：

输入：word1 = "sea", word2 = "eat"
输出：2
解释：第一步将 "sea" 变为 "ea"，第二步将 "eat" 变为 "ea" 。

欢迎大家一起答题！

蒋博文

1. def fun376(word1, word2):
   
2.     len1 = len(word1)
   
3.     len2 = len(word2)
   
4. 
   
5.     dp = [[0 for i in range(len2 + 1)] for j in range(len1 + 1)]
   
6.     dp[0][0] = 0
   
7.     for i in range(1,len2 + 1):
   
8.         dp[0][i] = dp[0][i - 1] + 1
   
9.     for i in range(1,len1 + 1):
   
10.         dp[i][0] = dp[i-1][0] + 1
    
11.         for j in range(1,len2 + 1):
    
12.             if word1[i-1] == word2[j - 1]:
    
13.                 dp[i][j] = dp[i - 1][j - 1]
    
14.             else:
    
15.                 dp[i][j] = min(dp[i - 1][j] + 1,dp[i][j - 1] + 1)
    
16.     return dp[len1][len2]

复制代码

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:06
@zltzlt 想问一下两个字符串是不是一样长？

应该是可以不一样长的吧。反正我这样写的。

kinkon

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

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

TJBEST

采用了一种算法，因为本人不太精通算法，不知道有没有成套的系统
我通过数学的数组递归得出的结论
f(i,j)表示从word1取前i元素构成字符串str1，word2取前j元素构成字符串str2时，可以从str1和str2中找到相同的子列的长度的最大值。（子列定义为：从字符串中选择若干字符并将他们按照在原有字符串的顺序拼接在一起组成的新字符串）
当word1[i-1]==word2[j-1] 显然为f(i,j)=f(i-1,j-1)+1
当word1[i-1]！=word2[j-1] 可知f(i-1,j)和f(i,j-1)至少有一个和f(i,j)相等且根据定义可知 f(i-m,j-n)<= f(i,j)(m,n都是非负数)存在。所以f(i,j)=min{f(i-1,j),f(i,j-1)}
最后的结果两个字符串总长度 减去 两倍保留的长度(保留的长度即f(len(word1),len(word2)，删完剩下的字符串长度)
上面的推导不是三言两语说明白的，语言能力有限

1. def fun376(word1,word2):
   
2.     M1 = len(word1)
   
3.     M2 = len(word2)
   
4.     previous = [0]*(M2+1)
   
5.     for i in range(1,M1+1):
   
6.         now = [0]
   
7.         for j in range(1,M2+1):
   
8.             if word1[i-1]==word2[j-1]:
   
9.                 now.append(previous[j]+1)
   
10.             else:
    
11.                 now.append(max(previous[j],now[-1]))
    
12.         previous = now[:]
    
13.     return M1+M2-previous[-1]*2

复制代码

旅途Z

楼主， word里的字符可以重复出现吗

zltzlt

旅途Z 发表于 2020-4-15 15:44
楼主， word里的字符可以重复出现吗

可以

zltzlt

kinkon 发表于 2020-4-15 14:06
@zltzlt 想问一下两个字符串是不是一样长？

不是一样长的

风魔孤行者

1. def f(word1,word2):
   
2.     a = len(word1)+len(word2)
   
3.     new_word = ''
   
4.     for each in range(len(word1)):
   
5.         word3 = word1[each:]
   
6.         word4 = word2
   
7.         new = ''
   
8.         for m in word3:
   
9.             if m in word4:
   
10.                 word4 = word4[word4.find(m)+1:]
    
11.                 new += m
    
12.         if len(new) > len(new_word):
    
13.             new_word = new
    
14.     return a-len(new_word)*2

复制代码

March2615

整理思路用了好久

1. # 解题思路：word1和word2剩余的一定是两者共有的word3(不一定连续，但一定在两遍都出现)
   
2. # 字符串的增删改操作 -> 动态规划
   
3. # 动态转移方程：
   
4. # 遍历word1和2，
   
5. # 一个字母如果在两个里面都有，则在word3中也有
   
6. # 否则，要么在1没有，要么在2没有
   
7. # 建立一个二维数组dp[len(word1)][len(word2)]
   
8. # dp[i][j]表示遍历word1[i]和word2[j]时word3的长度
   
9. # 若字母在两个里面都有，则 -> dp[i][j] = dp[i-1][j-1] + 1
   
10. # 否则，word3长度是dp[i-1][j]和dp[i][j-1]的较大值 -> dp[i][j] = max(dp[i-1][j], dp[i][j-1])

复制代码

1. def daily376(word1: str, word2: str) -> int:
   
2.     l1, l2 = len(word1), len(word2)
   
3.     dp = [[0 for _ in range(l2 + 1)] for _ in range(l1 + 1)]
   
4.     for i in range(1, l1 + 1):
   
5.         for j in range(1, l2 + 1):
   
6.             if word1[i - 1] == word2[j - 1]:
   
7.                 dp[i][j] = dp[i - 1][j - 1] + 1
   
8.             else:
   
9.                 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
   
10.     return l1 + l2 - 2 * dp[l1][l2]

复制代码

zltzlt

蒋博文 发表于 2020-4-15 13:36

199 ms

zltzlt

kinkon 发表于 2020-4-15 13:40

269 ms

zltzlt

TJBEST 发表于 2020-4-15 15:42
采用了一种算法，因为本人不太精通算法，不知道有没有成套的系统
我通过数学的数组递归得出的结论
f(i,j) ...

解答错误

输入：word1 = "ab", word2 = "a"
输出：3
预期结果：1

zltzlt

风魔孤行者 发表于 2020-4-15 18:01

解答错误

输入：

1. word1 = "intention", word2 = "execution"

复制代码

输出：10
预期结果：8

TJBEST

zltzlt 发表于 2020-4-15 20:52
解答错误

输入：word1 = "ab", word2 = "a"

已修改，见8楼@zltzlt

zltzlt

TJBEST 发表于 2020-4-15 21:15
已修改，见8楼@zltzlt

解答错误

输入：word1 = "food", word2 = "money"
输出：5
预期结果：7

TJBEST

zltzlt 发表于 2020-4-15 21:28
解答错误
输入：word1 = "food", word2 = "money"

@zltzlt
多改了一个-1，这次应该对了。

1. def fun376(word1,word2):
   
2.     M1 = len(word1)
   
3.     M2 = len(word2)
   
4.     previous = [0]*(M2+1)
   
5.     for i in range(1,M1+1):
   
6.         now = [0]
   
7.         for j in range(1,M2+1):
   
8.             if word1[i-1]==word2[j-1]:
   
9.                 now.append(previous[j-1]+1)
   
10.             else:
    
11.                 now.append(max(previous[j],now[-1]))
    
12.         previous = now[:]
    
13.     return M1+M2-previous[-1]*2

复制代码