Pythonで指定された制約を使用して、別の文字列から文字列を形成できるかどうかを確認します

2つの文字列小文字の文字列sとtがあるとします。次の制約を使用してsからtを生成できるかどうかを確認する必要があります-

• tの文字はsにあります。たとえば、tに2つの「a」がある場合、sにも2つの「a」が必要です。

• tのいずれかの文字がsにない場合は、前の2文字（前の2つのASCII値）がsにあるかどうかを確認します。たとえば、「f」がtに含まれているが、sには含まれていない場合、「d」と「e」をsから使用して「f」を作成できます。

したがって、入力がs ="pghn" t ="pin"の場合、「g」と「h」から「i」を作成して「pin」を作成できるため、出力はTrueになります。

これを解決するには、次の手順に従います-

• freq：=sの各文字の頻度
• 0からtのサイズの範囲のiについては、
  • freq [t [i]]がゼロ以外の場合、
    • freq [t [i]]：=freq [t [i]]-1
  • それ以外の場合、freq[t[i]の最初の前の文字]およびfreq[t [i]の2番目の前の文字]がゼロ以外の場合、
    • freq[t[i]の最初の前の文字]を1つ減らします
    • freq[t[i]の2番目の前の文字]を1つ減らします
  • それ以外の場合、
    • Falseを返す
• 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