Chương trình kiểm tra chuỗi gõ có phải do phím kẹt khi gõ chuỗi mục tiêu Python

Cho hai chuỗi s (chuỗi gõ thực tế) và t (chuỗi mục tiêu). Một số phím bị kẹt có thể làm ký tự xuất hiện 1 hoặc nhiều lần. Kiểm tra s có thể là kết quả gõ t với phím kẹt không.

Ví dụ: s="appppleee", t="apple" → True.

Giải thuật (Hai con trỏ)

1. i, j duyệt s, t; t_last lưu ký tự cuối khớp của t
2. Khi : tăng cả hai, cập nhật t_last
3. Khi : chỉ tăng i (ký tự lặp do phím kẹt)
4. Khác → False
5. Cuối: phần còn lại của s phải toàn t_last

Ví dụ triển khai

def solve(s, t):
    i = j = 0
    s_len, t_len = len(s), len(t)
    t_last = ""
    while j < t_len:
        if i == s_len:
            return False
        if s[i] == t[j]:
            t_last = t[j]
            i += 1
            j += 1
        elif s[i] == t_last:
            i += 1
        else:
            return False
    if i < s_len:
        return all(ch == t_last for ch in s[i:])
    return True

print(solve("appppleee", "apple"))

Đầu vào

"appppleee", "apple"

Đầu ra

True