97. Interleaving String

💡

Interleave

Định nghĩa đơn giản

Một chuỗi s3 được gọi là interleaving của s1 và s2 nếu:

s3 chứa tất cả các ký tự của s1 và s2 (không thiếu, không thừa),

Thứ tự các ký tự trong s1 và s2 phải được giữ nguyên trong s3,

Các ký tự của s1 và s2 có thể được xen kẽ với nhau theo bất kỳ cách nào, miễn là không đảo lộn thứ tự của từng chuỗi

Ví dụ minh họa

Giả sử:

s1 = "abc"

s2 = "def"

Các chuỗi sau là interleaving của s1 và s2:

"abcdef" (lấy hết s1 rồi hết s2)

"adbecf" (lấy a từ s1, d từ s2, b từ s1, e từ s2, c từ s1, f từ s2)

"dabecf" (d từ s2, a từ s1, b từ s1, e từ s2, c từ s1, f từ s2)

Nhưng "acbdef" không phải là interleaving, vì ký tự 'b' của s1 lại đứng sau 'c', làm sai thứ tự gốc của s1

Problem

Bài toán yêu cầu kiểm tra xem chuỗi s3 có thể được tạo ra bằng cách xen kẽ các ký tự từ hai chuỗi s1 và s2 mà vẫn giữ nguyên thứ tự các ký tự trong từng chuỗi không

Approach

Nếu tổng độ dài của s1 và s2 khác độ dài s3 , chắc chắn không thể interleave được, return false ngay

Sử dụng DP để lưu state:

dp[i][j] là true nếu có thể tạo được s3[0...i+j-1] từ s1[0..i-1] và s2[0..j-1].

Nếu ký tự tiếp theo của s1 khớp với ký tự tiếp theo của s3 và trạng thái trước đó (dp[i-1][j]) là true thì dp[i][j] = true

Nếu ký tự tiếp theo của s2 khớp với ký tự tiếp theo của s3 và trạng thái trước đó (dp[i][j-1]) là true thì dp[i][j] = true.

Khởi tạo dp = true (hai chuỗi rỗng tạo thành chuỗi rỗng)

Solution

typescripttypescript

1function isInterleave(s1: string, s2: string, s3: string): boolean {
2    const m = s1.length;
3    const n = s2.length;
4    if (m + n !== s3.length) return false;
5    const dp: boolean[][] = Array.from({ length: m + 1 }, () => Array(n + 1).fill(false))
6    dp[0][0] = true;
7    for (let i = 0; i <= m; i++) {
8        for (let j = 0; j <= n; j++) {
9            if (i > 0) dp[i][j] = dp[i][j] || (dp[i - 1][j] && s1[i - 1] === s3[i + j - 1])
10            if (j > 0) dp[i][j] = dp[i][j] || (dp[i][j - 1] && s2[j - 1] === s3[i + j - 1])
11        }
12    }
13    return dp[m][n]
14};

💡

dp[i][j] là trạng thái gì?

dp[i][j] lưu trạng thái: Có thể tạo ra s3[0…i+j-1] bằng cách lấy i ký tự đầu của s1 và j ký tự đầu của s2 hay không

Cụ thể

i là số ký tự đã lấy từ s1 (tức là đang xét đến ký tự s1[i - 1] nếu lấy tiếp)

j là số ký tự đã lấy từ s2 (tức là đang xét đến ký tự s2[j - 1] nếu lấy tiếp)

dp[i][j] = true nghĩa là: Có thể dùng s1[0..i-1] và s2[0..j-1] để xếp xen kẽ thành s3[0..i+j-1].

💡

Tại sao phải cần m + 1 và n +1?

Nếu chỉ khởi tạo mảng dp có kích thước m x n thì bạn không thể biểu diễn trạng thái khi chưa lấy ký tự nào từ s1 hoặc s2 (tức là i =0 và j = 0)

dp là trạng thái ban đầu: chưa lấy ký tự nào từ cả hai chuỗi (chuỗi rỗng)

dp[i] là trạng thái: Đã lấy i ký tự từ s1, chưa lấy ký tự nào từ s2

dp[j] là trạng thái: đã lấy j ký tự từ s2, chưa lấy ký tự nào từ s1

💡

Có thể chọn liên tiếp nhiều ký tự từ chuỗi s1 (hoặc s2) khi tạo ra chuỗi xen kẽ (interleave) - miễn là thứ tự của các ký tự trong từng chuỗi gốc được giữ nguyên

Cụ thể trong thuật toán DP interleaving string:

Ở mỗi trạng thái (i, j) bạn có hai lựa chọn

Nếu ký tự tiếp theo của s1 khớp với s3, bạn lấy tiếp ký tự đó từ s1 (tức là tăng i lên 1, giữ j)

Nếu ký tự tiếp theo của s2 khớp với s3, bạn lấy tiếp ký tự đó từ s2 (tức là tăng j lên 1, giữ i)

Bạn có thể liên tục lấy nhiều ký tự từ s1 (nếu chúng khớp với các ký tự tiếp theo của s3) rồi sau đó mới lấy từ s2, hoặc ngược lại

Không bắt buộc phải xen kẽ 1-1: giữa s1 và s2. Bạn có thể lấy 2,3 hoặc nhiều ký tự liên tiếp từ s1 (hoặc s2), miễn là tổng số ký tự đã lấy từ s1 và s2 đúng bằng vị trí hiện tại trên s3, và thứ tự của từng chuỗi không bị đảo lộn

Loading content...

1function isInterleave(s1: string, s2: string, s3: string): boolean { 2 const m = s1.length; 3 const n = s2.length; 4 if (m + n !== s3.length) return false; 5 const dp: boolean[][] = Array.from({ length: m + 1 }, () => Array(n + 1).fill(false)) 6 dp[0][0] = true; 7 for (let i = 0; i <= m; i++) { 8 for (let j = 0; j <= n; j++) { 9 if (i > 0) dp[i][j] = dp[i][j] || (dp[i - 1][j] && s1[i - 1] === s3[i + j - 1]) 10 if (j > 0) dp[i][j] = dp[i][j] || (dp[i][j - 1] && s2[j - 1] === s3[i + j - 1]) 11 } 12 } 13 return dp[m][n] 14};

97. Interleaving String

Related Posts

Related Posts

97. Interleaving String

Related Posts

2. Add Two Numbers

3. Longest Substring Without Repeating Characters

3. Longest Substring Without Repeating Characters

4. Median of Two Sorted Arrays

5. Longest Palindromic Substring

6. Zigzag Conversion

9. Palindrome Number

11. Container With Most Water

12. Integer to Roman

13. Roman to Integer

14. Longest Common Prefix

17. Letter Combinations of a Phone Number

19. Remove Nth Node From End of List

20. Valid Parentheses

21. Merge Two Sorted Lists

Related Posts

2. Add Two Numbers

3. Longest Substring Without Repeating Characters

3. Longest Substring Without Repeating Characters

4. Median of Two Sorted Arrays

5. Longest Palindromic Substring

6. Zigzag Conversion

9. Palindrome Number

11. Container With Most Water

12. Integer to Roman

13. Roman to Integer

14. Longest Common Prefix

17. Letter Combinations of a Phone Number

19. Remove Nth Node From End of List

20. Valid Parentheses

21. Merge Two Sorted Lists