Python：每日一题 376
本帖最后由 zltzlt 于 2020-4-15 13:36 编辑今天的题目：
给定两个字符串 word1 和 word2，找到使得 word1 和 word2 相同所需的最小操作数，每一个操作可以删除任意一个字符串中的一个字符。
示例：
输入：word1 = "sea", word2 = "eat"
输出：2
解释：第一步将 "sea" 变为 "ea"，第二步将 "eat" 变为 "ea" 。
{:10_298:}欢迎大家一起答题！{:10_298:} 本帖最后由 蒋博文 于 2020-4-15 14:56 编辑
def fun376(word1, word2):
len1 = len(word1)
len2 = len(word2)
dp = [ for j in range(len1 + 1)]
dp = 0
for i in range(1,len2 + 1):
dp = dp + 1
for i in range(1,len1 + 1):
dp = dp + 1
for j in range(1,len2 + 1):
if word1 == word2:
dp = dp
else:
dp = min(dp + 1,dp + 1)
return dp 本帖最后由 kinkon 于 2020-4-15 14:31 编辑
def f376(word1, word2):
n1, n2 = len(word1), len(word2)
dp = * (n2 + 1)
for i in range(n1 + 1):
temp = * (n2 + 1)
for j in range(n2 + 1):
if i == 0 or j == 0:
temp = i + j
elif word1 == word2:
temp = dp
else:
temp = min(dp, temp) + 1
dp = temp[:]
#print(dp)
return dp 占楼 @zltzlt 想问一下两个字符串是不是一样长？ kinkon 发表于 2020-4-15 14:06
@zltzlt 想问一下两个字符串是不是一样长？
应该是可以不一样长的吧。反正我这样写的。 蒋博文 发表于 2020-4-15 14:57
应该是可以不一样长的吧。反正我这样写的。
嗯嗯，我也是这样想的，字符串一样长的话会简单些 本帖最后由 TJBEST 于 2020-4-15 21:14 编辑
采用了一种算法，因为本人不太精通算法，不知道有没有成套的系统
我通过数学的数组递归得出的结论
f(i,j)表示从word1取前i元素构成字符串str1，word2取前j元素构成字符串str2时，可以从str1和str2中找到相同的子列的长度的最大值。（子列定义为：从字符串中选择若干字符并将他们按照在原有字符串的顺序拼接在一起组成的新字符串）
当word1==word2 显然为f(i,j)=f(i-1,j-1)+1
当word1！=word2 可知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)，删完剩下的字符串长度)
上面的推导不是三言两语说明白的，语言能力有限{:5_109:}
def fun376(word1,word2):
M1 = len(word1)
M2 = len(word2)
previous = *(M2+1)
for i in range(1,M1+1):
now =
for j in range(1,M2+1):
if word1==word2:
now.append(previous+1)
else:
now.append(max(previous,now[-1]))
previous = now[:]
return M1+M2-previous[-1]*2 楼主， word里的字符可以重复出现吗 旅途Z 发表于 2020-4-15 15:44
楼主， word里的字符可以重复出现吗
可以 kinkon 发表于 2020-4-15 14:06
@zltzlt 想问一下两个字符串是不是一样长？
不是一样长的 本帖最后由 风魔孤行者 于 2020-4-15 18:23 编辑
def f(word1,word2):
a = len(word1)+len(word2)
new_word = ''
for each in range(len(word1)):
word3 = word1
word4 = word2
new = ''
for m in word3:
if m in word4:
word4 = word4
new += m
if len(new) > len(new_word):
new_word = new
return a-len(new_word)*2 本帖最后由 March2615 于 2020-4-15 22:04 编辑
整理思路用了好久
# 解题思路：word1和word2剩余的一定是两者共有的word3(不一定连续，但一定在两遍都出现)
# 字符串的增删改操作 -> 动态规划
# 动态转移方程：
# 遍历word1和2，
# 一个字母如果在两个里面都有，则在word3中也有
# 否则，要么在1没有，要么在2没有
# 建立一个二维数组dp
# dp表示遍历word1和word2时word3的长度
# 若字母在两个里面都有，则 -> dp = dp + 1
# 否则，word3长度是dp和dp的较大值 -> dp = max(dp, dp)
def daily376(word1: str, word2: str) -> int:
l1, l2 = len(word1), len(word2)
dp = [ for _ in range(l1 + 1)]
for i in range(1, l1 + 1):
for j in range(1, l2 + 1):
if word1 == word2:
dp = dp + 1
else:
dp = max(dp, dp)
return l1 + l2 - 2 * dp 蒋博文 发表于 2020-4-15 13:36
199 ms kinkon 发表于 2020-4-15 13:40
269 ms TJBEST 发表于 2020-4-15 15:42
采用了一种算法，因为本人不太精通算法，不知道有没有成套的系统
我通过数学的数组递归得出的结论
f(i,j) ...
解答错误
输入：word1 = "ab", word2 = "a"
输出：3
预期结果：1 风魔孤行者 发表于 2020-4-15 18:01
解答错误
输入：word1 = "intention", word2 = "execution"
输出：10
预期结果：8 zltzlt 发表于 2020-4-15 20:52
解答错误
输入：word1 = "ab", word2 = "a"
已修改，见8楼@zltzlt TJBEST 发表于 2020-4-15 21:15
已修改，见8楼@zltzlt
解答错误
输入：word1 = "food", word2 = "money"
输出：5
预期结果：7 本帖最后由 TJBEST 于 2020-4-15 21:41 编辑
zltzlt 发表于 2020-4-15 21:28
解答错误
输入：word1 = "food", word2 = "money"
@zltzlt
多改了一个-1，这次应该对了。{:5_104:}
def fun376(word1,word2):
M1 = len(word1)
M2 = len(word2)
previous = *(M2+1)
for i in range(1,M1+1):
now =
for j in range(1,M2+1):
if word1==word2:
now.append(previous+1)
else:
now.append(max(previous,now[-1]))
previous = now[:]
return M1+M2-previous[-1]*2
页:
[1]
2