数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学检查Python中是否可以使用给定约束条件从另一个字符串形成一个字符串
假设我们有两个小写字符串s和t。我们必须检查是否可以使用以下约束条件从s生成t：
t的字符存在于s中，例如，如果t中有两个'a'，则s中也应该有两个'a'。
当t中的任何字符不在s中时，检查s中是否存在前两个字符（前两个ASCII值）。例如，如果'f'在t中但不在s中，则可以使用s中的'd'和'e'来构成'f'。
因此，如果输入类似于s = "pghn" t = "pin"，则输出将为True，因为我们可以使用'g'和'h'来构成'i'从而构成"pin"。
为了解决这个问题，我们将遵循以下步骤：
- freq := s中每个字符的频率
- 对于范围0到t的大小，执行以下操作：
- 如果freq[t[i]]不为零，则
- freq[t[i]] := freq[t[i]] - 1
- 否则，如果freq[t[i]的前一个字符]和freq[t[i]的前两个字符]不为零，则
- 将freq[t[i]的前一个字符]减少1
- 将freq[t[i]的前两个字符]减少1
- 否则，
- 返回False
- 如果freq[t[i]]不为零，则
- 返回True
让我们看看下面的实现，以便更好地理解：
示例
from collections import defaultdict def solve(s, t): freq = defaultdict(lambda:0) for i in range(0, len(s)): freq[s[i]] += 1 for i in range(0, len(t)): if freq[t[i]]: freq[t[i]] -= 1 elif (freq[chr(ord(t[i]) - 1)] and freq[chr(ord(t[i]) - 2)]): freq[chr(ord(t[i]) - 1)] -= 1 freq[chr(ord(t[i]) - 2)] -= 1 else: return False return True s = "pghn" t = "pin" print(solve(s, t))
输入
"pghn", "pin"
输出
True
更新于：2020-12-29
260 次查看
广告