Kiểm tra xem chuỗi có thể tạo từ chuỗi khác với ràng buộc cho trước hay không trong Python

Giả sử chúng ta có hai chuỗi chữ thường s và t. Cần kiểm tra xem t có thể tạo ra từ s với các ràng buộc sau:

• Các ký tự của t phải có trong s (ví dụ t có 2 'a' thì s cũng phải có 2 'a').
• Nếu ký tự trong t không có trong s, kiểm tra xem 2 ký tự trước đó (theo mã ASCII) có trong s không. Ví dụ 'f' không có trong s nhưng 'd' và 'e' có, thì có thể dùng 'd' và 'e' để tạo 'f'.

Ví dụ, s = "pghn", t = "pin", đầu ra True vì có thể tạo 'i' từ 'g' và 'h' để tạo "pin".

Các bước giải quyết:

• freq := tần suất ký tự trong s.
• Duyệt i từ 0 đến độ dài t-1:
  • Nếu freq[t[i]] > 0: giảm freq[t[i]] đi 1.
  • Ngược lại nếu freq[chr(ord(t[i])-1)] > 0 và freq[chr(ord(t[i])-2)] > 0: giảm cả hai đi 1.
  • Ngược lại, trả về False.
• Trả về True.

Xem ví dụ dưới đây để hiểu rõ hơn:

Ví dụ

from collections import defaultdict

def solve(s, t):
    freq = defaultdict(lambda: 0)
    for ch in s:
        freq[ch] += 1
    for ch in t:
        if freq[ch]:
            freq[ch] -= 1
        elif freq[chr(ord(ch) - 1)] and freq[chr(ord(ch) - 2)]:
            freq[chr(ord(ch) - 1)] -= 1
            freq[chr(ord(ch) - 2)] -= 1
        else:
            return False
    return True

s = "pghn"
t = "pin"
print(solve(s, t))

Đầu vào

"pghn", "pin"

Đầu ra

True