โปรแกรมเช็คว่าสตริงเป้าหมายสร้างได้จากการรวมสองสตริงหรือไม่ใน Python

คำอธิบายโจทย์

ให้สตริง s, t, r ตรวจสอบว่า r สามารถสร้างได้จากการ interleaving (รวมสลับกัน) ตัวอักษรของ s และ t โดยรักษาลำดับสัมพัทธ์ภายในแต่ละสตริง

ตัวอย่าง

s = "xyz", t = "mno", r = "xymnoz" → True (x จาก s, y จาก s, mno จาก t, z จาก s)

วิธีแก้ปัญหา

Recursive DP (Memoization):

1. ถ้าทั้งสามว่าง → True
2. ถ้า r ว่างแต่ s/t ไม่ว่าง → False
3. ถ้า s ว่าง → ตรวจ t == r
4. ถ้า t ว่าง → ตรวจ s == r
5. ลอง match ตัวแรกของ r กับ s[0] หรือ t[0] แล้ว recurse

โค้ด Python

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))

อินพุต

"xyz", "mno", "xymnoz"

เอาต์พุต

True