小牛的作业

[编程题]小牛的作业

热度指数：312 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

某个下午，小牛在写作业，写着写着就哭了。因为作业上有这样一道题。

给你两个仅包含小写英文字母的字符串 $s$ 和 $t$ ，你可以对字符串 $s$ 执行以下操作：

删除字符串中任意一个元素。
将字符串中任意一个元素转变为任意一个字母。

现需要将字符串 $s$ 转变为 $t'$ ， $t'$ 中所有字符的出现次数和 $t$ 相同。

求将字符串 $s$ 转变成 $t'$ 的最小操作次数。若无解，则输出 -1 。

你能帮帮小牛吗？

输入描述:

输入包含两行。

第一行为仅包含小写英文字母的字符串 $s$ 。
第二行为仅包含小写英文字母的字符串 $t$ 。

$1 \leq s.length \leq 10^5$
$1 \leq t.length \leq 10^5$

输出描述:

一个整数，表示将字符串 $s$ 转变成 $t'$ 的最小操作次数。若无解，则输出 -1。

示例1

输入

abc
cde

输出

说明

仅需两步操作就能将  转变为 。
第一步，将  的第一个字符 'a' 转变为 'd'。
第二步，将  的第二个字符 'b' 转变为 'e'。

示例2

输入

abc
cdef

输出

-1

说明

不存在任意一组操作能将  转变为 。

算法知识视频讲解

不要熬夜zZ

import sys

for index, line in enumerate(sys.stdin):
a = line.split()
if index == 0:
s = a[0]
else:
t = a[0]

hashmap = dict()

for char in t:
if char not in hashmap:
hashmap[char] = 1
else:
hashmap[char] += 1
res = 0
if (len(s) - len(t)) >= 0:
for char in s:
if char in hashmap and hashmap[char] > 0:
hashmap[char] -= 1
else:
res += 1
else:
res = -1

print(res)

发表于今天 17:36:12 回复(0)