30daychallenge (26) | Longest Common Subsequence

Given two strings text1 and text2, return the length of their longest common subsequence.

A subsequence of a string is a new string generated from the original string with some characters(can be none) deleted without changing the relative order of the remaining characters. (eg, "ace" is a subsequence of "abcde" while "aec" is not). A common subsequence of two strings is a subsequence that is common to both strings.

If there is no common subsequence, return 0.

Example 1:

Input: text1 = "abcde", text2 = "ace" 
Output: 3  
Explanation: The longest common subsequence is "ace" and its length is 3.

Example 2:

Input: text1 = "abc", text2 = "abc"
Output: 3
Explanation: The longest common subsequence is "abc" and its length is 3.

Example 3:

Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: There is no such common subsequence, so the result is 0.

Constraints:

• 1 <= text1.length <= 1000
• 1 <= text2.length <= 1000
• The input strings consist of lowercase English characters only.

Tôi từng khá nhạy cảm với các giới hạn đề bài, căn cứ vào giới hạn của một bài lập trình thi đấu có thể sẽ là tôi biết bài toán này sẽ phải được giải quyết bằng phương pháp như thế nào. Giả sử giới hạn là 10e3 như trên, tôi biết rằng cách tốt nhất để giải bài toán này có lẽ là dùng hai vòng for O(N*N), nếu 10e6, chắc chắn phải làm một thuật toán O(N) rồi, còn 10e9, chắc chắn phải dùng một thuật toán tối thiểu là O(NlogN). Còn 10e18, tin tôi đi, bài này chắc chắn sẽ là xử lý bit.

Quay trở về đề bài, dãy con giống nhau dài nhất là một bài toán kinh điển được giải bằng phương pháp Quy hoạch động. Nếu là xưa tôi sẽ khởi tạo một mảng 2 chiều, vậy bài toán này sẽ mất O(N*M) thời gian và O(N*M) không gian. Nhưng hiện nay tôi có thể giảm không gian xuống còn O(N).

Để làm điều đó tôi chỉ cần 1 ma trận với 2 dòng và N cột [2][N]. Tại ta chỉ cần biết cột cần tổng hợp hiện thời và cột trước đó. Nhưng trước tiên, hãy nói về công thức truy hồi:

dp[i][j] = dq[i-1][j-1] + 1 if text[i] = text[j] | max(dq[i][j-1],dq[i-1][j]

Vẽ cái bảng ra là thấy ngay nhé, còn chứng minh thì tra Google nha.

Trong phép toán bit, ta đã biết để kiểm tra 1 số có chia hết cho một số hay không thì dùng N & (N-1). Với chia hết cho 2 sẽ dùng N&1, luôn trả về 1 và 2. Vâng và ta sẽ dùng nó để linh hoạt trong việc định vị cột mà ta đang đứng. Ví dụ: uni=i&1 -> dq[uni][j], hàng còn lại là dq[1-uni][j]. Với cách làm này, không cần phải duyệt update một hàng nào đó nữa, mọi thứ có vẻ rất linh hoạt.

Hết rồi, hẹn gặp lại các bạn vào ngày mai !