Kiểm tra biến đổi chuỗi s thành t bằng cách viết hoa và xóa chữ thường (Python)

Bài toán: Cho chuỗi s (có chữ hoa/thường) và t (chỉ chữ hoa). Có thể: (1) viết hoa một số chữ thường trong s, (2) xóa tất cả chữ thường còn lại. Kiểm tra có thể biến s thành t không.

Dynamic Programming

dp[i][j] = có thể khớp i ký tự đầu của s với j ký tự đầu của t không.

Triển khai Python

def solve(s, t):
    n, m = len(s), len(t)
    dp = [[False] * (m + 1) for _ in range(n + 1)]
    dp[0][0] = True
    
    for i in range(n):
        for j in range(m + 1):
            if dp[i][j]:
                # Option 1: viết hoa s[i] khớp t[j]
                if j < m and s[i].upper() == t[j]:
                    dp[i + 1][j + 1] = True
                # Option 2: xóa s[i] (chỉ nếu s[i] là chữ thường)
                if s[i].islower():
                    dp[i + 1][j] = True
    
    return dp[n][m]

# Test
print(solve("fanToM", "TOM"))      # True: f,a,n → xóa; T,o→O,M → TOM
print(solve("Hello", "HELLO"))     # True: viết hoa tất cả
print(solve("Hello", "HEL"))       # True: xóa 'l','o'
print(solve("Hello", "WORLD"))     # False

Kết quả

True

Giải thích

• dp[i][j] = True nghĩa là dùng i ký tự đầu của s có thể tạo ra j ký tự đầu của t.
• Chuyển trạng thái: nếu dp[i][j] True, thì:
  • Nếu s[i].upper() == t[j] → có thể match, set dp[i+1][j+1] = True.
  • Nếu s[i] là chữ thường → có thể xóa, set dp[i+1][j] = True.
• Kết quả ở dp[n][m].
• Độ phức tạp: O(n×m) time, O(n×m) space (có thể tối ưu O(m)).