Đã đăng vào thg 5 7, 4:48 CH 13 phút đọc

[Dynamic Programming] Quá trình mình giải bài leetcode "Interleaving String"

MayFest2024

Hello mọi người, mấy hôm nay mình đang rảnh nên mò mẩm tìm hiểu và luyện một số bài leetcode về quy hoạch động - Dynamic Programing thì tình cờ chạm mặt bài Interleaving String - không rõ mọi người như thế nào nhưng mình đã mất nhiều thời gian để hiểu và thực hiện bài này hic hic. Nên mình viết bài này để chia sẻ về quá trình làm bài toán này của mình. Cùng làm với mình nhé !!!

Đề bài

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

Mô tả bài toán

Đầu vào ta có hai chuỗi s1, s2 và s3. Kiểm tả xem chuỗi s3 có được xem là interleaving ( chuỗi xen kẽ) của s1 và s2 hay không.

Chú ý: rằng một chuỗi s3 được xem là interleaving (xen kẽ) của s1 và s2 chỉ khi s3 chứa toàn bộ ký tự từ s1 và s2 nhưng thứ tự các ký tự của từng chuỗi riêng lẻ đó vẫn giữ nguyên. Để cho dễ hình dung thì hãy nhìn ví dụ dưới đây nhé:

Ví dụ

Example 1:
Input: S1 = "xxyzz", S2 = "wwyyzzzx" and S3 = "xxwwyyzzyzzxz"
Output: true
Explanation:"xx" (từ S1) + "wwyyzz" (từ S2) + "yz" (từ S1) + "zx" (từ S2) + "z" (từ S1)

Example 2
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output: false
Explanation: Chú ý rằng không có cách nào tách s2 để hợp thành s3 từ s1 và s2 được do đoạn "ca" nằm ở s2 không thỏa được bất kỳ phần nào của "s3" do thứ tự của các ký tự "ca" phải giữ nguyên.

Tiếp cận vấn đề

Okay, giờ thì ........ bắt đầu như thế nào nhỉ ?

loading_cat

Để phân tích thử một chút từ ví dụ đầu trên, để xem quá trình kiểm tra xen kẽ diễn ra như thế nào nhé:

Input: S1 = "xxyzz", S2 = "wwyyzzzx" and S3 = "xxwwyyzzyzzxz"

Step 1: Đầu tiên ta lấy s3 kiểm tra lần lượt với s1 và s2 theo từng ký tự. Ở đoạn đầu của s3 match với s1 đoạn "xx" nè. Ta xóa đoạn match đó ra khỏi chuỗi. Giờ ta còn s1 là "yzz" và s2 là "wwyyzzzx" và s3 là "wwyyzzyzzxz".
Step 2: Tiếp theo, giờ thì những ký tự đầu ở s1 không còn match với s3 nữa mà là s2 match ở đoạn "wwyyzz". Tương tự như step trên, ta xóa đoạn match đó thì còn s1 là "yzz" và s2 là "zx" và s3 là "yzzxz".
Step 3: Lặp lại như trên thì match ở đoạn "yzz" sau đó ta có s1 chỉ còn là "" và s2 là "zx" và s3 là "xz".

Dừng lại một chút, nếu vậy thì "s2" với "s3" đâu có match nhau ( chú ý ràng buộc thứ tự các ký tự của từng chuỗi riêng lẻ đó vẫn phải giữ nguyên nhé - "zx" khác với "xz"). Như vậy thì kết quả phải là false chứ nhỉ ?
Không hẳn, nhiều khi là do đây không phải là cách xếp xen kẽ duy nhất, ta sẽ lùi lại vài bước để xem bước nào có thể thay đổi ký tự được tách ra, à, quay lại step 3 xem
Step 3a: Ta sẽ không lấy cả đoạn match ở đoạn "yzz" mà chỉ sẽ match s3 với s2 ở đoạn "yz" thôi thì ta có s1 chỉ còn là "z" và s2 là "zx" và s3 là "zxz".
Này, giờ có vẻ đúng rồi đấy, sau đó lần lượt ta có kết quả là s1: "z", s2: "", s3: "z" rồi cuối cùng là tada! cả ba chuỗi s1, s2, s3 đều rỗng, và đây là chuỗi xen kẽ interleaving string hợp lệ.

Ồ, như vậy là đã có sự lặp lại xảy ra ( ở bước 3 và bước 3a), vậy thì mình có thể sử dụng recursive function ở đây nè ( đệ quy ).

Tiếp cận vấn đề

1. Sử dụng đệ quy - Recursive Function

Tổng kết lại thì các có 2 khả năng sau:

Nếu ký tự đầu tiên của s3 match với ký tự đầu tiên của s1, chúng ta di chuyển đến ký tự tiếp theo trong s1 và s3 và gọi đệ quy hàm.
Nếu ký tự đầu tiên của s3 match với ký tự đầu tiên của s1, chúng ta di chuyển đến ký tự tiếp theo trong s1 và s3 và gọi đệ quy hàm.

Vậy thì các bước để giải quyết bài toán như sau :

Nếu s1, s2 và s3 là rỗng, sau đó trả về True - chuỗi hợp lệ. Điều này sẽ là base case cho hàm đệ quy, chuỗi s3 trống là interleaving của s1 và s2.
Nhưng nếu s3 là rỗng nhưng một trong s1 và s2 không rỗng - tức là không thỏa interleaving do vẫn còn ký tự ở cả chuỗi ban đầu - tả về False, Fact thú vị: điều này cũng có nghĩa là số kỷ tự s3 nhỏ hơn của s1 + s2

Cuối cùng là với hai khả năng đã thảo luận ở trên, tức là khả năng match với ký tự s1 hoặc match với ký tự s2 ( chú ý là hoặc nhé)

Nếu s3[0] == s1[0], sau đó kiểm tra cho s1[1…], s2, s3[1...]
Nếu s3[0] == s2[0] thì kiểm tra cho s1, s2[1…], s3[1…]

Nếu bất kỳ trong hai khả năng được đề cập ở trên là đúng, sau đó trả về true, nếu không thì trả về false.

OK, vậy là mình hiểu sơ sơ về flow rồi, nào làm thôi, ở đây mình sẽ dùng Python nhé:

    def isInterleave(self, s1, s2, s3):
        """
        :type s1: str
        :type s2: str
        :type s3: str to check
        :rtype: bool
        """
        # Check lengths of each string
        s1Len, s2Len, s3Len = len(s1), len(s2), len(s3)
        
        # Base cases
        if s1Len == 0 and s2Len == 0 and s3Len == 0:
            return True
        if s3Len == 0:
            return False

        # Recursive calls
        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

Okay, có vẻ ổn, bỏ vào leetcode chạy thử nào, pass các testcase example rồi, submit rồi ngồi đợi ....... Fail vài testcases rồi, check thử xem fail testcase nào

Time Limit Exceed

Time Limit Exceed ở code Python sao ???😂có vẻ là code của mình có vấn đề rồi, để xem thử độ phức tạp là bao nhiều - do mỗi ký tự chỉ có 2 khả năng nên độ phức tạp time complexity sẽ là $O(2^n)$ !!!

2. Sử dụng Dynamic Programming

Như vậy là cách dùng đệ quy chạy ok, nhưng mà nó lâu quá, phải tính cách khác thôi Hmmm, mình đang học và luyện dynamic programming mà, phải dùng dynamic programming chứ. Nào để xem, mình phải tách bài toán thành những bài toán nhỏ hơn - cụ thể ở đây là chuỗi nhỏ hơn nè, mình sẽ có bảng DP table sẽ là lưu ....... cái gì nhỉ ?

Quay lại một chút, ở cách tiếp cận vấn đề ta thấy một điều là với cách kiểm tra lần lượt theo từng ký tự như vậy thì vô hình chung ta đang xây dựng path cho bài toán đấy. Mình sẽ xây dựng một cái bảng cho dễ hình dung:

Input: S1 = "xxyzz", S2 = "wwyyzzzx" and S3 = "xxwwyyzzyzzxz"

                    |    w    |    w    |    y    |    y    |    z    |      z      |      z      |      x       |
          |   0(i)  |    1    |    2    |    3    |    4    |    5    |      6      |      7      |      8       |
    --------------------------------------------------------------------------------------------------------------
      0(j)|   ""    |         |         |         |         |         |             |             |              |
    |     |    |    |         |         |         |         |         |             |             |              |      
  x | 1   |    x    |         |         |         |         |         |             |             |              |
    |     |    |    |         |         |         |         |         |             |             |              | 
  x | 2   |   xx    -  xxw    -  xxww   -  xxwwy  -  xxwwyy - xxwwyyz -  xxwwyyzz   |             |              |
    |     |         |         |         |         |         |         |     |       |             |              |
  y | 3   |         |         |         |         |         |         |  xxwwyyzzy  -  xxwwyyzzyz |              |
    |     |         |         |         |         |         |         |     |       |      |      |              |
  z | 4   |         |         |         |         |         |         |  xxwwyyzzyz - xxwwyyzzyzz - xxwwyyzzyzzx |
    |     |         |         |         |         |         |         |     |       |             |      |       | 
  z | 5   |         |         |         |         |         |         | xxwwyyzzyzz |             | xxwwyyzzyzzxz|

Cái bảng của chúng ta sẽ như sau:

Số dòng của bảng chính là số ký tự của s1
Số cột của bảng chính là số ký tự của s2
Mỗi ô trong bảng chính là ký tự của s3 đang được duyệt và cho thấy xem ký tự đó của s1,s2 có được xem là match với ký tự s3 tại ô đó hay không.
Các giá trị của ô hình thành nên path thể hiện trạng thái interleaving của chuỗi s3 theo từng ký tự
i và j là index tương ứng với s2 và s1

Bảng của chúng ta sẽ có vài điểm cần chú ý như sau:

Do phải giữ nguyên thứ tự các ký tự nên bảng này sẽ đi theo từ trái -> phải, từ trên -> dưới ( hay nói cách khác, path của s3 chỉ có thể đi xuống hoặc phải - điều này quan trọng vì tức là giá trị của ô sẽ phụ thuộc với những ô bên trái [ i-1 ] và ô bên trên [ j-1 ] )
Tại vị trí (0, 0), cả S1 và S2 đều rỗng, chính là điểm bắt đầu.
Tại đó ta bắt đầu duyệt từng ký tự của s3, xem ký tự đó của s1,s2 tại vị trí đó có match với ký tự s3 không và giá trị của ô bên trái ( hoặc bên trên ) có đang được xem là interleaving (xen kẽ) hay không. Nếu thỏa cả 2 điều kiện thì ta sẽ đánh dấu ô đó là interleaving.

Ví dụ:
Tại vị trí (2, 3), nó cho thấy rằng bằng cách xem xét tới ký tự thứ 5 của S3, interleaving có thể của S1 và S2 có thể là "xxwwy" và được hình thành từ "xx" (s1) và "wwy" (s2). Với ký tự thứ 5 "y" của "s3" match với ký tự thứ 3 "y" của s2 và ô bên trái vị trí (2, 2) xem là interleaving nên vị trí (2, 3) được xem là interleaving.
Tại vị trí (4, 7), giá trị của "xxwwyyzzyzz" của s3 có thể hình thành từ 2 cách: "xx" (s1) + "wwyyzz" (s2) + "yz" (s1) + "z" (s2) và "xx" (s1) + "wwyyzz" (s2) + "y" (s1) + "z" (s2) + "z" (s1). Với ký tự thứ 5 "y" của "s3" match với ký tự thứ 3 "y" của s2 và ô bên trái vị trí (4, 6) xem là interleaving, cũng như ô bên trên vị trí (3, 7) xem là interleaving nên vị trí (4, 7) được xem là interleaving.
Tại vị trí (5,8), vị trí cuối cùng trong bảng - cũng chính là ký tự cuối cùng của s3, tại đây ký tự z match với dòng "z" của s1 và do vị trí bên trên(4,8) được xem là interleaving nên vị trí này được xem là interleaving -> kết thúc bài toán với giá trị True

Có thể mình viêt hơi khó hiểu nhưng hy vọng mọi người sẽ hiểu cái bảng hay ý tưởng thì sẽ hình dung ra vấn đề.

Và từ đây ta cũng sẽ có mảng array 2 chiều DP = [][] hoạt động như trên bảng. Mảng này sẽ cho biết sẽ cho biết liệu s3 có được xem là interleaving tại i + j - 1 index ( ta phải - 1 ở đây vì ta không tính index 0 là chuỗi rỗng) khi s1 tại index j và s2 tại index i. Index 0 ở đây là chuỗi rỗng ( giả sử ta đặt s1 theo chiều dọc và s2 theo chiều ngang nhé )

Ta sẽ thực hiện bằng cách duyệt theo từng ô trong mảng ( với index i, j sẽ có ký tự tương ứng s1, s2, s3). Nếu tại vị trí mà ký tự s2 của index i-1 ( nhớ là -1 nhé ) match với ký tự s3 tương ứng và vị trí ( j, i - 1) - ô bên trái - là interleaving thì sẽ được xem là Interleaving - đánh dấu True. Tương tự, nếu tại vị trí mà ký tự s1 của index j-1 match với ký tự s3 tương ứng và vị trí ( j - 1 , i ) - ô bên trên - là interleaving thì sẽ được xem là Interleaving. Còn nếu không thỏa bất kỳ điều kiện nào thì bỏ qua ( với khởi tạo các giá trị ban đầu là False)

Kết quả của bài toán chính là giá trị của mảng tại vị trị cuối cùng.

Hơi đuối rồi, nhưng giờ là chỉ còn bước viết code thôi, cố lên nào:

def isInterleave(self, s1, s2, s3):
    """
    :type s1: str
    :type s2: str
    :type s3: str
    :rtype: bool
    """
    # Get the lengths of input strings
    s1Len = len(s1)
    s2Len = len(s2)

    # If the total length of s1 and s2 is not equal to the length of s3,
    # they cannot be interleaved
    if s1Len + s2Len != len(s3):
        return False

    # If either s1 or s2 is empty, check if s3 is equal to the non-empty string
    if s1Len == 0 or s2Len == 0:
        return s1 == s3 or s2 == s3

    # Initialize a DP table with dimensions (s1Len+1) x (s2Len+1)
    dp = [[False] * (s2Len + 1) for _ in range(s1Len + 1)]

    # Initialize the first cell of dp table as empty string is considered interleaving
    dp[0][0] = True

    # Fill in the DP table
    for i in range(s1Len + 1):
        for j in range(s2Len + 1):
            k = j + i - 1

            # Skip if k is out of bounds
            if k == -1:
                continue

            # In top-most cells: only check the left cell value 
            if i == 0:
                dp[i][j] = dp[i][j - 1] and s2[j - 1] == s3[k]
            # In left-most cells: only check the top cell value 
            elif j == 0:
                dp[i][j] = dp[i - 1][j] and s1[i - 1] == s3[k]
            # Otherwise, check both s1 and s2
            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 the value in the bottom-right corner of the DP table
    return dp[s1Len][s2Len]

Yes, hy vọng lần này sẽ được, bỏ vào Leetcode chay, submit và tada, pass hết các testcases rồi. Yay !

Kết thúc

Như vậy đó là toàn bộ quá trình mình đã tìm hiểu và thực hiện bài leetcode Interleaving String. Có thể với nhiều người bài này không quá khó, nhưng với mình thì mình đã dành khá nhiều thời gian cho bài này vì thế mình ghi lại trải nghiệm của mình và chia sẻ ở đây với hy vọng là giúp ích cho mọi người. Cảm ơn mọi người đã dành thời gian đọc tới đây nhé.

Happy Cod.....

Khoan, ở cuối đề bài ở dưới có vẻ còn gì đó:

Follow up: Could you solve it using only O(s2.length) additional memory space? ( giải bài toán nhưng chỉ sử dụng lượng ô nhớ với độ dài chuỗi s2)

Mình thấy này cũng khá hay, ý tưởng cũng là phát triển tiếp tục từ cách giải trên nhưng bài viết chắc chỉ tới đây thôi nhé. Code đang chạy ổn nên chỉ tới đây thôi.

1st rule of programming: if it works ..... don't touch it! .....

Nhưng nếu mọi người cần thì mình sẽ tiếp tục ở phần comment nhé. Đây cũng là bài đầu tay của mình nên rất mong những phản hồi của các bạn để mình làm tốt hơn. Cảm ơn mọi người !

Happy coding

References:

Algorithm LeetCode Dynamic programming