Kiểm tra chuỗi có tuân theo thứ tự ký tự của mẫu trong Python

Cho chuỗi s và chuỗi mẫu t (không có ký tự trùng lặp). Kiểm tra xem các ký tự trong s có xuất hiện theo cùng thứ tự như trong t hay không.

Ví dụ: s = "hello world", t = "hw" → 'h' xuất hiện trước 'w' trong s → True.

Giải thuật

• Nếu độ dài s < t → False.
• Với mỗi cặp ký tự liên tiếp trong t (x, y), tìm chỉ số cuối cùng của x và chỉ số đầu tiên của y trong s.
• Nếu chỉ số cuối của x > chỉ số đầu của y → vi phạm thứ tự → False.

Mã ví dụ

def solve(s, t):
    if len(s) < len(t):
        return False
    for i in range(len(t) - 1):
        x = t[i]
        y = t[i + 1]
        right = s.rindex(x)
        left = s.index(y)
        if right == -1 or left == -1 or right > left:
            return False
    return True

s = "hello world"
t = "hw"
print(solve(s, t))

Đầu vào

"hello world", "hw"

Đầu ra

True