Editorial for Máy In Kẹt Phím
Submitting an official solution before solving the problem yourself is a bannable offence.
Author: Nghaiz
Lời giải: Máy In Nhãn Kẹt Phím
Chủ đề: xử lý chuỗi (string), duyệt bằng for
Tóm tắt đề
Cho tên \(s\) và nhãn \(t\). Mỗi ký tự của \(s\) khi gõ sẽ được in ra \(1\) hoặc nhiều lần liên tiếp. Hỏi \(t\) có thể là kết quả in của \(s\) hay không.
Nhận xét then chốt: chia chuỗi thành các "nhóm"
Gom các ký tự giống nhau đứng liền nhau thành nhóm, mỗi nhóm ghi lại (ký tự, số lần lặp):
anna→(a,1) (n,2) (a,1)aanaa→(a,2) (n,1) (a,2)
Khi gõ một nhóm \((c, k)\) trong tên, nhân viên nhấn phím \(c\) đúng \(k\) lần, mỗi lần in ra ít nhất một chữ \(c\). Kết quả là một nhóm \((c, k')\) trong nhãn với \(k' \geq k\). Hai nhóm liền nhau trong tên có ký tự khác nhau, nên khi in ra chúng không bao giờ dính vào nhau.
Vậy \(t\) là nhãn hợp lệ của \(s\) khi và chỉ khi:
- \(s\) và \(t\) có cùng số nhóm;
- nhóm thứ \(i\) của hai chuỗi có cùng ký tự;
- số lần lặp trong nhóm thứ \(i\) của \(t\) không nhỏ hơn của \(s\).
Cài đặt
def nen(s):
nhom = []
for ch in s:
if nhom and nhom[-1][0] == ch:
nhom[-1][1] += 1
else:
nhom.append([ch, 1])
return nhom
Sau đó so sánh từng cặp nhóm bằng zip. Có thể dùng itertools.groupby cho gọn:
from itertools import groupby
nhom = [(c, len(list(g))) for c, g in groupby(s)]
Độ phức tạp
\(O(|s| + |t|)\) cho mỗi câu hỏi, tổng cộng tuyến tính theo kích thước input.
Code mẫu
import sys
def nen(s):
nhom = []
for ch in s:
if nhom and nhom[-1][0] == ch:
nhom[-1][1] += 1
else:
nhom.append([ch, 1])
return nhom
def co_the_in(ten, nhan):
a, b = nen(ten), nen(nhan)
if len(a) != len(b):
return False
for (c1, k1), (c2, k2) in zip(a, b):
if c1 != c2 or k2 < k1:
return False
return True
def main():
data = sys.stdin.read().split()
t = int(data[0])
kq = []
for i in range(t):
ten, nhan = data[1 + 2 * i], data[2 + 2 * i]
kq.append("YES" if co_the_in(ten, nhan) else "NO")
print("\n".join(kq))
main()
Comments