Bài 20 Leetcode: Valid Parentheses

Đề bài:

Cho một chuỗi s chứa các ký tự ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ và ‘]’, xác định xem chuỗi đầu vào có hợp lệ hay không.

Một chuỗi đầu vào được coi là hợp lệ nếu:

1. Các dấu ngoặc mở phải được đóng bằng cùng loại dấu ngoặc.
2. Các dấu ngoặc mở phải được đóng theo đúng thứ tự.
3. Mỗi dấu ngoặc đóng phải có một dấu ngoặc mở tương ứng cùng loại.

Ví dụ 1:

Input: s = "()"
Output: true

Ví dụ 2:

Input: s = "()[]{}"
Output: true

Ví dụ 3:

Input: s = "(]"
Output: false

Ràng buộc:

• 1 <= độ dài chuỗi s <= 10^4
• s chỉ chứa các dấu ngoặc đơn ‘()[]{}’.

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

class Solution {
 public:
  bool isValid(string s) {
    stack<char> stack;

    for (const char c : s)
      if (c == '(')
        stack.push(')');
      else if (c == '{')
        stack.push('}');
      else if (c == '[')
        stack.push(']');
      else if (stack.empty() || pop(stack) != c)
        return false;

    return stack.empty();
  }

 private:
  int pop(stack<char>& stack) {
    const int c = stack.top();
    stack.pop();
    return c;
  }
};

Đâ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 để kiểm tra xem một chuỗi đầu vào có hợp lệ hay không trong việc sử dụng các dấu ngoặc đơn ‘()’, ‘[]’, ‘{}’ mở và đóng.

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

1. Phương thức `isValid` nhận đầu vào là một chuỗi `s` để kiểm tra tính hợp lệ.

2. Khởi tạo một ngăn xếp (stack) có kiểu dữ liệu là `char`.

3. Sử dụng vòng lặp for để duyệt qua từng ký tự `c` trong chuỗi `s`.

4. Nếu `c` là dấu ngoặc mở ‘(‘, ‘{‘, ‘[‘ thì đẩy vào ngăn xếp dấu ngoặc đóng tương ứng ‘)’, ‘}’, ‘]’.

5. Nếu `c` không phải là dấu ngoặc mở, ta kiểm tra xem ngăn xếp có rỗng không hoặc ký tự đầu tiên trong ngăn xếp khác với `c`. Nếu điều này xảy ra, chuỗi không hợp lệ và ta trả về false.

6. Sau khi duyệt qua toàn bộ chuỗi `s`, kiểm tra xem ngăn xếp có rỗng không. Nếu không rỗng, tức là vẫn còn các dấu ngoặc mở chưa được đóng, do đó chuỗi không hợp lệ và ta trả về false. Ngược lại, nếu ngăn xếp rỗng, chuỗi hợp lệ và ta trả về true.

7. Phương thức `pop` được sử dụng để lấy ra ký tự đầu tiên từ ngăn xếp và xóa nó khỏi ngăn xếp.

Thuật toán này sử dụng ngăn xếp để kiểm tra tính hợp lệ của chuỗi dấu ngoặc. Khi gặp một dấu ngoặc mở, ta đẩy dấu ngoặc đóng tương ứng vào ngăn xếp. Khi gặp một dấu ngoặc đóng, ta kiểm tra xem dấu ngoặc đóng đó có khớp với ký tự đầu tiên trong ngăn xếp không. Nếu không khớp, chuỗi không hợp lệ. Sau khi duyệt qua toàn bộ chuỗi, nếu ngăn xếp rỗng thì chuỗi hợp lệ, ngược lại là không hợp lệ.

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

class Solution {
  public boolean isValid(String s) {
    Deque<Character> stack = new ArrayDeque<>();

    for (final char c : s.toCharArray())
      if (c == '(')
        stack.push(')');
      else if (c == '{')
        stack.push('}');
      else if (c == '[')
        stack.push(']');
      else if (stack.isEmpty() || stack.pop() != c)
        return false;

    return stack.isEmpty();
  }
}

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

class Solution:
  def isValid(self, s: str) -> bool:
    stack = []

    for c in s:
      if c == '(':
        stack.append(')')
      elif c == '{':
        stack.append('}')
      elif c == '[':
        stack.append(']')
      elif not stack or stack.pop() != c:
        return False

    return not stack