Bài 32 Leetcode: Longest Valid Parentheses

Đề bài:

Cho một chuỗi chỉ chứa các ký tự ‘(‘ và ‘)’, trả về độ dài của chuỗi con ngoặc đúng (được hình thành đúng) dài nhất.

Ví dụ 1:

Input: s = "(()"
Output: 2
Giải thích: Chuỗi con ngoặc đúng dài nhất là "()".

Ví dụ 2:

Input: s = ")()())"
Output: 4
Giải thích: Chuỗi con ngoặc đúng dài nhất là "()()".

Ví dụ 3:

Input: s = ""
Output: 0

Ràng buộc:

• 0 <= độ dài của chuỗi s <= 3 * 10^4
• s[i] là ‘(‘, hoặc ‘)’.

Giải thích thuật toán bằng C ++

class Solution {
 public:
  int longestValidParentheses(string s) {
    const string s2 = ")" + s;
    // dp[i] := the length of the longest valid parentheses in the substring
    // s2[1..i]
    vector<int> dp(s2.length());

    for (int i = 1; i < s2.length(); ++i)
      if (s2[i] == ')' && s2[i - dp[i - 1] - 1] == '(')
        dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 2;

    return ranges::max(dp);
  }
};

Đoạn mã trên triển khai thuật toán để tìm độ dài của dãy ngoặc đúng dài nhất trong một chuỗi.

Thuật toán này hoạt động như sau:

1. Tạo chuỗi `s2` bằng cách thêm một ký tự đặc biệt vào đầu chuỗi `s`. Ký tự này sẽ đảm bảo rằng tất cả các dãy ngoặc đúng bắt đầu từ vị trí 1 của `s2` (loại bỏ trường hợp ngoặc đúng nằm ở đầu chuỗi `s`).

2. Khởi tạo một mảng `dp` có cùng độ dài với `s2`, trong đó `dp[i]` đại diện cho độ dài của dãy ngoặc đúng dài nhất trong đoạn con `s2[1..i]`.

3. Duyệt qua từng ký tự của `s2`, bắt đầu từ vị trí 1 đến cuối chuỗi.

4. Nếu ký tự tại vị trí `i` là `’)’` và ký tự tại vị trí `i – dp[i – 1] – 1` là `'(‘`, có nghĩa là ta đã tìm thấy một dãy ngoặc đúng. Ta cập nhật `dp[i]` bằng cách tính toán độ dài của dãy ngoặc đúng tại vị trí `i`.

– `dp[i]` được tính bằng `dp[i – 1] + dp[i – dp[i – 1] – 2] + 2`. Độ dài của dãy ngoặc đúng tại vị trí `i` được tính bằng tổng độ dài của dãy ngoặc đúng tại vị trí `i – 1`, độ dài của dãy ngoặc đúng trước dãy ngoặc đúng tại vị trí `i`, và 2 (độ dài của dãy ngoặc đúng hiện tại).

5. Trả về giá trị lớn nhất trong mảng `dp` là độ dài của dãy ngoặc đúng dài nhất trong chuỗi `s`.

Ví dụ, nếu chuỗi `s` là `”()(()”`, sau khi áp dụng thuật toán, giá trị trả về sẽ là 2, tương ứng với dãy ngoặc đúng `”()”` trong chuỗi.

Giải thích thuật toán bằng Java

class Solution {
  public int longestValidParentheses(String s) {
    final String s2 = ")" + s;
    // dp[i] := the length of the longest valid parentheses in the substring
    // s2[1..i]
    int dp[] = new int[s2.length()];

    for (int i = 1; i < s2.length(); ++i)
      if (s2.charAt(i) == ')' && s2.charAt(i - dp[i - 1] - 1) == '(')
        dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 2;

    return Arrays.stream(dp).max().getAsInt();
  }
}

Giải thích thuật toán bằng Python

class Solution:
  def longestValidParentheses(self, s: str) -> int:
    s2 = ')' + s
    # dp[i] := the length of the longest valid parentheses in the substring
    # s2[1..i]
    dp = [0] * len(s2)

    for i in range(1, len(s2)):
      if s2[i] == ')' and s2[i - dp[i - 1] - 1] == '(':
        dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 2

    return max(dp)