Chương trình kiểm tra hai câu có tương tự nhau trong Python

Mô tả bài toán

Cho hai câu s và t chỉ chứa chữ cái tiếng Anh. Hai câu được gọi là tương tự nếu có thể chèn một câu tùy ý (có thể rỗng) vào một trong hai câu để chúng trở nên giống nhau.

Ví dụ

Nếu đầu vào là s = "we live at city Kolkata", t = "city Kolkata", thì đầu ra là True vì có thể thêm "we live at" vào t để được s.

Giải thuật

1. Tách câu thành danh sách từ: s1 = s.split(), s2 = t.split().
2. Nếu len(s1) > len(s2), hoán đổi s1 và s2.
3. Trong khi s1 không rỗng:
   • Nếu từ đầu của s1 và s2 giống nhau: xóa từ đầu cả hai.
   • Ngược lại nếu từ cuối của s1 và s2 giống nhau: xóa từ cuối cả hai.
   • Ngược lại: trả về False.
4. Trả về True.

Triển khai Python

def solve(s, t):
    s1 = s.split()
    s2 = t.split()
    if len(s1) > len(s2):
        s1, s2 = s2, s1
    while s1:
        if s2[0] == s1[0]:
            s2.pop(0)
            s1.pop(0)
        elif s2[-1] == s1[-1]:
            s2.pop()
            s1.pop()
        else:
            return False
    return True

s = "we live at city Kolkata"
t = "city Kolkata"
print(solve(s, t))

Đầu vào

"we live at city Kolkata", "city Kolkata"

Đầu ra

True