[Dynamic Programming] Hướng dẫn giải bài Leetcode 'Interleaving String'

Xin chào mọi người, gần đây mình có thời gian rảnh rỗi và quyết định tìm hiểu về bài toán Leetcode liên quan đến quy hoạch động (Dynamic Programming) mang tên 'Interleaving String'. Điều này khiến mình tốn không ít thời gian để hiểu rõ vấn đề. Vì vậy, mình viết bài này để chia sẻ quá trình giải quyết bài toán này và hy vọng có thể giúp đỡ được ai đó trong quá trình luyện tập.

Đề bài

Mình sẽ để link dưới đây cho những ai muốn làm chung với mình nhé: Leetcode - Interleaving String.

Mô tả bài toán

Bài toán yêu cầu kiểm tra xem chuỗi s3 có phải là kết quả của việc hoán đổi xen kẽ giữa hai chuỗi s1 và s2 hay không. Cụ thể, s3 phải chứa tất cả các ký tự từ s1 và s2 mà vẫn giữ nguyên thứ tự của các ký tự trong mỗi chuỗi.

Ví dụ:

Ví dụ 1:

• Input: S1 = "xxyzz", S2 = "wwyyzzzx" và S3 = "xxwwyyzzyzzxz"
• Output: true
• Giải thích: "xx" (từ S1) + "wwyyzz" (từ S2) + "yz" (từ S1) + "zx" (từ S2) + "z" (từ S1)

Ví dụ 2:

• Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
• Output: false
• Giải thích: Không có cách nào để tách s2 để hợp thành s3 vì đoạn "ca" không thỏa mãn tính thứ tự của "s3".

Tiếp cận vấn đề

Giờ mình sẽ bắt đầu phân tích cách kiểm tra sự xen kẽ giữa các chuỗi. Đầu tiên, mình sẽ sử dụng phương pháp đệ quy.

1. Phương pháp đệ quy

Ta sẽ tạo một hàm đệ quy có nhiệm vụ kiểm tra sự trùng khớp giữa các ký tự của chuỗi s3 với s1 và s2. Cụ thể, nếu ký tự đầu tiên của s3 trùng với ký tự đầu tiên của s1, ta sẽ gọi hàm đệ quy với phần còn lại của s1 và s3. Tương tự nếu ký tự đầu tiên của s3 trùng với ký tự đầu tiên của s2.

Đoạn mã Python:

def isInterleave(self, s1, s2, s3):
    s1Len, s2Len, s3Len = len(s1), len(s2), len(s3)
    if s1Len + s2Len != s3Len:
        return False
    if not s1Len and not s2Len and not s3Len:
        return True
    if s3Len == 0:
        return False
    if s1Len > 0 and s3[0] == s1[0]:
        if self.isInterleave(s1[1:], s2, s3[1:]):
            return True
    if s2Len > 0 and s3[0] == s2[0]:
        if self.isInterleave(s1, s2[1:], s3[1:]):
            return True
    return False

Tuy nhiên, phương pháp này gặp phải vấn đề vì có thể xảy ra tình trạng vượt quá thời gian cho phép do độ phức tạp thời gian là O(2^n).

2. Phương pháp quy hoạch động (Dynamic Programming)

Vì vậy, mình sẽ áp dụng quy hoạch động để giải quyết bài toán một cách hiệu quả hơn. Ý tưởng là chúng ta sẽ xây dựng một bảng DP lưu trữ trạng thái của từng ký tự của chuỗi s3 trong mối liên hệ với các ký tự của s1 và s2.

Đoạn mã Python:

def isInterleave(self, s1, s2, s3):
    s1Len = len(s1)
    s2Len = len(s2)
    if s1Len + s2Len != len(s3):
        return False
    dp = [[False] * (s2Len + 1) for _ in range(s1Len + 1)]
    dp[0][0] = True
    for i in range(s1Len + 1):
        for j in range(s2Len + 1):
            k = j + i - 1
            if i == 0:
                dp[i][j] = dp[i][j - 1] and s2[j - 1] == s3[k]
            elif j == 0:
                dp[i][j] = dp[i - 1][j] and s1[i - 1] == s3[k]
            else:
                dp[i][j] = (dp[i][j - 1] and s2[j - 1] == s3[k]) or (dp[i - 1][j] and s1[i - 1] == s3[k])
    return dp[s1Len][s2Len]

Khi chạy đoạn mã trên, kết quả của bảng DP sẽ cho ta biết liệu s3 có được xem là sự xen kẽ của s1 và s2 hay không.

Kết luận

Trên đây là toàn bộ quá trình mình đã tìm hiểu và thực hiện bài Leetcode 'Interleaving String'. Mặc dù bài toán không quá khó, nhưng mình đã dành khá nhiều thời gian để giải quyết. Hy vọng rằng bài viết sẽ giúp những ai đang gặp khó khăn trong việc giải bài toán này. Cảm ơn mọi người đã đọc bài viết này, nếu có thắc mắc hay muốn chia sẻ kinh nghiệm của mình, hãy để lại bình luận bên dưới nhé. Chúc mọi người coding vui vẻ!
source: viblo