Chương trình kiểm tra chuỗi có thể chuyển thành chuỗi khác bằng cách xóa 1 ký tự trong Python

Cho hai chuỗi và , kiểm tra có thể xóa đúng 1 ký tự từ để được hay không.

Ví dụ: , → True (xóa 'o').

Giải thuật (Thử xóa từng vị trí O(n²))

1. Duyệt từ 0 đến :
   • Tạo .
   • Nếu : trả về .
2. Trả về .

Có thể tối ưu O(n) bằng hai con trỏ.

Ví dụ minh họa

class Solution:
    def solve(self, s, t):
        i = 0
        n = len(s)
        while i < n:
            temp = s[:i] + s[i+1:]
            if temp == t:
                return True
            i += 1
        return False

ob = Solution()
s = "world"
t = "wrld"
print(ob.solve(s, t))  # Output: True

Đầu vào

"world", "wrld"

Đầu ra

True