ตรวจสอบว่าแปลง String หนึ่งเป็นอีก String ได้หรือไม่ภายใต้เงื่อนไขด้วย Python

สมมติมี String s และ t (t เป็น Uppercase) ต้องตรวจสอบว่าแปลง s -> t ได้โดย: 1) เปลี่ยน Lowercase บางตัวเป็น Uppercase 2) ลบ Lowercase ที่เหลือทั้งหมด

เช่น Input s = "fanToM", t = "TOM" Output True (เปลี่ยน o->O ลบตัวอื่น)

ขั้นตอนแก้ (DP):

• DP[i][j] = สามารถสร้าง t[:j] จาก s[:i] ได้หรือไม่
• DP[0][0] = True
• Transition: ถ้า DP[i][j] และ s[i].upper() == t[j] -> DP[i+1][j+1] = True; ถ้า s[i] เป็น Lowercase -> DP[i+1][j] = True (ลบ)

ตัวอย่างโค้ด

def solve(s,t):
    n = len(s)
    m = len(t)
    dp= [[False for i in range(m+1)] for i in range(n+1)]
    dp[0][0] = True
    for i in range(len(s)):
        for j in range(len(t)+1):
            if dp[i][j] == True:
                if j < len(t) and (s[i].upper() == t[j]):
                    dp[i + 1][j + 1] = True
                if s[i].isupper()==False:
                    dp[i + 1][j] = True
    return dp[n][m]

s = "fanToM"
t = "TOM"
print(solve(s, t))

Input

"fanToM", "TOM"

Output

True