Chương trình kiểm tra chuỗi cuối có thể tạo từ hai chuỗi khác trong Python

Cho ba chuỗi s, t, r. Kiểm tra có thể tạo r bằng cách xen kẽ ký tự từ s và t theo thứ tự không.

Ví dụ: s = "xyz", t = "mno", r = "xymnoz" → True.

Giải pháp

Đệ quy với memo (hoặc DP 2D):

• Base case: cả ba rỗng → True; r rỗng nhưng s/t không → False
• Nếu s rỗng: trả về t == r
• Nếu t rỗng: trả về s == r
• Nếu s[0] == r[0] và solve(s[1:], t, r[1:]) → True
• Nếu t[0] == r[0] và solve(s, t[1:], r[1:]) → True
• Ngược lại False

Ví dụ minh họa

class Solution:
    def solve(self, s, t, r):
        if not s and not t and not r:
            return True
        if not r:
            return False
        if not s:
            return t == r
        if not t:
            return s == r
        if s[0] == r[0]:
            if self.solve(s[1:], t, r[1:]):
                return True
        if t[0] == r[0]:
            if self.solve(s, t[1:], r[1:]):
                return True
        return False

ob = Solution()
s = "xyz"
t = "mno"
r = "xymnoz"
print(ob.solve(s, t, r))

Đầu vào

"xyz", "mno", "xymnoz"

Đầu ra

True