Python에서 주어진 제약 조건을 사용하여 다른 문자열에서 문자열을 구성할 수 있는지 확인

두 개의 문자열 소문자 문자열 s와 t가 있다고 가정합니다. 다음 제약 조건을 사용하여 s에서 t를 생성할 수 있는지 여부를 확인해야 합니다. -

• 예를 들어 t에 2개의 'a'가 있으면 s에도 2개의 'a'가 있어야 합니다.

• t의 문자가 s에 없으면 이전 두 문자(이전 두 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]]가 0이 아니면
    • 주파수[t[i]] :=주파수[t[i]] - 1
  • 그렇지 않고 freq[t[i]의 첫 번째 이전 문자] 및 freq[t[i]의 두 번째 이전 문자]가 0이 아닌 경우
    • freq[t[i]의 첫 번째 이전 문자]를 1만큼 감소
    • freq[t[i]의 두 번째 이전 문자]를 1만큼 감소
  • 그렇지 않으면
    • 거짓을 반환
• 참 반환

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

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