Bài 22 Leetcode: Generate Parentheses

Đề bài:

Cho n cặp dấu ngoặc đơn, viết một hàm để tạo ra tất cả các tổ hợp của các dấu ngoặc đơn hợp lệ.

Ví dụ 1:

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

Ví dụ 2:

Input: n = 1
Output: ["()"]

Ràng buộc:

  • 1 <= n <= 8

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

class Solution {
 public:
  vector<string> generateParenthesis(int n) {
    vector<string> ans;
    dfs(n, n, "", ans);
    return ans;
  }

 private:
  void dfs(int l, int r, string&& path, vector<string>& ans) {
    if (l == 0 && r == 0) {
      ans.push_back(path);
      return;
    }

    if (l > 0) {
      path.push_back('(');
      dfs(l - 1, r, move(path), ans);
      path.pop_back();
    }
    if (l < r) {
      path.push_back(')');
      dfs(l, r - 1, move(path), ans);
      path.pop_back();
    }
  }
};

Đây là một phương thức trong một lớp được gọi là `Solution`. Phương thức này được sử dụng để tạo ra tất cả các tổ hợp của các dấu ngoặc đơn hợp lệ cho n cặp dấu ngoặc.

Dưới đây là cách thuật toán hoạt động:

1. Phương thức `generateParenthesis` nhận đầu vào là một số nguyên `n`, đại diện cho số cặp dấu ngoặc.

2. Khởi tạo một vector `ans` để lưu trữ tất cả các tổ hợp của dấu ngoặc.

3. Gọi phương thức `dfs` với tham số ban đầu là `n` cặp dấu ngoặc bên trái và `n` cặp dấu ngoặc bên phải, một chuỗi `path` rỗng và vector `ans`.

4. Phương thức `dfs` có vai trò duyệt qua tất cả các tổ hợp của dấu ngoặc.

5. Nếu `l` (số cặp dấu ngoặc bên trái) và `r` (số cặp dấu ngoặc bên phải) đều bằng 0, tức là đã tạo thành một tổ hợp hợp lệ của dấu ngoặc. Ta thêm `path` vào vector `ans` và kết thúc đệ quy.

6. Nếu `l` còn lớn hơn 0, ta thêm dấu ngoặc mở ‘(‘ vào `path`, giảm giá trị của `l` đi 1 và gọi đệ quy phương thức `dfs` với các tham số tương ứng. Sau đó, ta loại bỏ dấu ngoặc mở từ `path` để tiếp tục tạo các tổ hợp khác.

7. Nếu `l` nhỏ hơn `r`, tức là đã có dấu ngoặc mở được thêm vào `path`, ta thêm dấu ngoặc đóng ‘)’ vào `path`, giảm giá trị của `r` đi 1 và gọi đệ quy phương thức `dfs` với các tham số tương ứng. Sau đó, ta loại bỏ dấu ngoặc đóng từ `path` để tiếp tục tạo các tổ hợp khác.

8. Sau khi kết thúc phương thức `dfs`, trả về vector `ans` chứa tất cả các tổ hợp của dấu ngoặc hợp lệ.

Thuật toán này sử dụng phương pháp đệ quy (dfs) để tạo ra tất cả các tổ hợp của dấu ngoặc hợp lệ. Ta duyệt qua các trường hợp có thể xảy ra: thêm dấu ngoặc mở hoặc dấu ngoặc đóng vào `path`, và điều chỉnh số lượng cặp dấu ngoặc bên trái và bên phải tương ứng. Quá trình đệ quy được thực hiện cho đến khi `l` và `r` đều bằng 0, và tại đó ta có một tổ hợp hợp lệ của dấu ngoặc.

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

class Solution {
  public List<String> generateParenthesis(int n) {
    List<String> ans = new ArrayList<>();
    dfs(n, n, new StringBuilder(), ans);
    return ans;
  }

  private void dfs(int l, int r, final StringBuilder sb, List<String> ans) {
    if (l == 0 && r == 0) {
      ans.add(sb.toString());
      return;
    }

    if (l > 0) {
      sb.append("(");
      dfs(l - 1, r, sb, ans);
      sb.deleteCharAt(sb.length() - 1);
    }
    if (l < r) {
      sb.append(")");
      dfs(l, r - 1, sb, ans);
      sb.deleteCharAt(sb.length() - 1);
    }
  }
}

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

class Solution:
  def generateParenthesis(self, n):
    ans = []

    def dfs(l: int, r: int, s: str) -> None:
      if l == 0 and r == 0:
        ans.append(s)
      if l > 0:
        dfs(l - 1, r, s + '(')
      if l < r:
        dfs(l, r - 1, s + ')')

    dfs(n, n, '')
    return ans

 

Leave a Reply

Your email address will not be published. Required fields are marked *

PHP Code Snippets Powered By : XYZScripts.com
.
.
.
.