Kiểm tra xem một chuỗi có thể được hình thành từ một chuỗi khác bằng cách sử dụng các ràng buộc nhất định trong Python hay không

Giả sử chúng ta có hai chuỗi viết thường là chuỗi s và t. Chúng ta phải kiểm tra xem liệu t có thể được tạo ra từ s bằng cách sử dụng các ràng buộc sau hay không -

• Các ký tự của t có trong s, chẳng hạn nếu có hai chữ 'a' trong chữ t, thì chữ s cũng phải có hai chữ 'a.

• Khi bất kỳ ký tự nào trong t không có trong s, hãy kiểm tra xem hai ký tự trước đó (hai giá trị ASCII trước đó) có ở trong s hay không. Ví dụ:nếu 'f' ở trong t mà không phải ở s, thì 'd' và 'e' có thể được sử dụng từ s để tạo thành 'f'.

Vì vậy, nếu đầu vào giống như s ="pghn" t ="pin", thì đầu ra sẽ là True vì chúng ta có thể tạo 'i' từ 'g' và 'h' thành "pin".

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• freq:=tần suất của mỗi ký tự tính bằng s
• đối với tôi trong phạm vi từ 0 đến kích thước của t, thực hiện
  • nếu freq [t [i]] khác 0, thì
    • freq [t [i]]:=freq [t [i]] - 1
  • ngược lại khi freq [ký tự trước đó đầu tiên của t [i]] và freq [ký tự trước thứ hai của t [i]] khác 0, thì
    • giảm tần suất [ký tự trước đó đầu tiên của t [i]] xuống 1
    • giảm freq [ký tự thứ hai trước đó của t [i]] xuống 1
  • nếu không,
    • trả về Sai
• trả về True

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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))

Đầu vào

"pghn", "pin"

Đầu ra

True