检查是否可以使用 Python 中的给定约束从另一个字符串形成一个字符串

假设我们有两个小写字符串 s 和 t。我们必须检查是否可以使用以下约束从 s 生成 t -

• t 的字符在 s 中，例如如果 t 中有两个 'a'，那么 s 也应该有两个 'a'。

• 当 t 中的任何字符不在 s 中时，检查前两个字符（前两个 ASCII 值）是否在 s 中。例如，如果 'f' 在 t 中但不在 s 中，那么 'd' 和 'e' 可以从 s 中生成 'f'。

因此，如果输入类似于 s = "pghn" t = "pin"，那么输出将为 True，因为我们可以从 'g' 和 'h' 生成 'i' 以生成“pin”。

让我们看看以下实现以获得更好的理解 -

示例

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