Tác giả: Lê Trung Kiên lớp java 08
Email: lekien.2803.cg@gmail.com
SĐT: 0942096947
Link bài toán: https://leetcode.com/problems/valid-parentheses/
1. Mở đầu
Xin chào các bạn, mình viết ra bài viết này để chia sẻ phương pháp giải cũng như tư duy của mình về bài toán này của leetcode. Phương pháp của mình có thể không phải là tối ưu nhất, tuy nhiên mình sẽ phân tích, chia nhỏ bài toán ra thành các module nhỏ hơn để dễ giải quyết cũng như giúp các bạn hiểu được các yêu cầu mà bài toán đưa ra.
2. Đề bài
Cho một chuỗi s trong đó chứa các kí tự (, ), {, }, [ và ]. Hãy kiểm tra xem chuỗi s có phải chuỗi hợp lệ với các tiêu chí sau:
Dấu ngoặc mở phải được đóng bằng dấu ngoặc cùng loại.
Dấu ngoặc mở phải được đóng theo đúng thứ tự.
Mỗi dấu ngoặc đóng có một dấu ngoặc mở tương ứng cùng loại.
Điều kiện:
1 <= s.length <= 10^4.schỉ bao gồm các dấu ngoặc đơn'()[]{}'.
Ví dụ 1:
Input: s = "()"
Output: true
Ví dụ 2:
Input: s = "()[]{}"
Output: true
Ví dụ 3:
Input: s = "(]"
Output: false
3. Phân tích
Âu kê, bài này thì không quá phức tạp, bây giờ chúng ta cùng bóc tách đề bài nhé.
Với dạng bài này, tôi đang nghĩ tới cấu trúc dữ liệu stack, các phần tử sẽ được lưu và truy cập theo cách FILO (Frist In Last Out) tức là nhập trước xuất sau.
Theo đề bài, dấu ngoặc mở phải được đóng bởi dấu ngoặc cùng loại, bên cạnh đó dấu ngoặc mở phải được đóng theo đúng thứ tự. Nên chúng ta sẽ làm như sau:
- Chúng ta sẽ duyệt lần lượt từ đầu tới cuối chuỗi
s. - Mỗi khi chúng ta gặp một dấu ngoặc mở
(,{,[thì ta sẽ nhét một dấu ngoặc đóng),},]tương ứng vào trongstack. - Đến khi gặp dấu ngoặc đóng
),},]trong chuỗi, chúng ta sẽ lấy dữ liệu trên cùng củastackđể so sánh xem nó có phải là dấu ngoặc tương ứng phải đóng theo thứ tự hay không, nếu đúng thì ta sẽ xóa nó khỏistackvà tiếp tục kiểm tra. - Cuối cùng, ta sẽ kiểm tra xem
stackcó rỗng không? Nếu nó rỗng, tức là các ngoặc mở đã được đóng theo đúng thứ tự, đúng chủng loại, còn nếu không thì trả vềfalsethôi. - Còn một lưu ý nữa, theo điều kiện đề bài chỉ nói rằng độ dài của chuỗi
schỉ từ1đến10^4và không gì khác. Tuy nhiên ta có thể suy luận thêm, nêu độ dài củaslà lẻ, tức là có dấu mở mà không có đóng hoặc có đóng mà không có mở. Vậy thì ta trả vềfalseluôn và không cần xét gì nữa.
4. Code chạy bằng cơm
- Ô kê, hãy thử chạy với ví dụ
s= "{[]}"nhé, chúng ta sẽ duyệt từ đầu tới cuối chuỗis, cùng với đó là mộtstacktrống dùng để chứa các dấu ngoặc đóng.
Tại vị tríi = 0, ta thấy có dấu ngoặc mở{, vậy thì ta sẽ thêm dấu ngoặc đóng tương ứng vàostack:
Tại vị trí i = 1, ta thấy dấu ngoặc mở [, vậy thì ta lại thêm dấu ngoặc đóng tương ứng vào stack:
Tại vị trí i = 2, khi này ta không gặp dấu ngoặc mở nữa, vậy thì ta sẽ lấy phần tử trên cùng của stack ra đem so sánh với dấu ngoặc hiện tại luôn:
Nếu hai ngoặc này giống nhau, nghĩa là ngoặc đã được đóng theo đúng thứ tự và đúng loại với ngoặc mở, ta di chuyển đến phần tử tiếp theo:
Cuối cùng, sau khi lấy hết phần tử stack ra để kiểm tra rồi, nếu stack trống, nghĩa là s chính là chuỗi hợp lệ theo yêu cầu đề bài.
- Hãy cùng xem một ví dụ khác nhé:
s = "{[}]", chúng ta vẫn sẽ làm như trên
Tại vị tríi = 0, ta thấy có dấu ngoặc mở{, vậy thì ta sẽ thêm dấu ngoặc đóng tương ứng vàostack:
Tại vị trí i = 1, ta thấy dấu ngoặc mở [, vậy thì ta lại thêm dấu ngoặc đóng tương ứng vào stack:
Tại vị trí i = 2, khi này ta không gặp dấu ngoặc mở nữa, vậy thì ta sẽ lấy phần tử trên cùng của stack ra đem so sánh với dấu ngoặc hiện tại luôn. Và trong trường hợp này, dấu ngoặc đóng ở chuỗi s là }, còn dấu ngoặc đóng ở stack chúng ta lấy ra được là ], nghĩa là chuỗi s này có dấu đóng tuy cùng loại nhưng không theo thứ tự, trả về false luôn:
- Giờ xét thêm một trường hợp đặc biệt nữa:
s = "}[", với trường hợp này dấu đóng lại ở vị trí ngay đầu tiên, chúng ta mới chỉ xét các trường hợp dấu ngoặc mở nằm phía trước, khi nàystacksẽ không có phần tử nào để lấy ra mà so sánh với dấu ngoặc đóng}này, như vậy sẽ xảy lỗi.
Để khắc phục điều này, chúng ta sẽ thêm điều kiện kiểm tra xem stack có phần tử nào không, nếu không có, tức dấu ngoặc chúng ta đang xét là dấu đóng mà lại không có dấu mở trước đó, nên ta sẽ trả về false.
5. Code bằng máy
Code của chúng ta sẽ như sau:
public boolean isValid(String s) {
if (s.length() % 2 != 0) {
return false;
}
Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
stack.push(')');
}
else if (s.charAt(i) == '[') {
stack.push(']');
}
else if (s.charAt(i) == '{') {
stack.push('}');
}
else if (stack.isEmpty() || stack.pop() != s.charAt(i)){
return false;
}
}
return stack.isEmpty();
}
6. Kết thúc
Qua bài viết này, mình đã chia sẻ cho các bạn cách mình tư duy khi giải bài tập trên leetcode. Hi vọng bài viết giúp ích cho các bạn trong cách tư duy để giải các bài tập khác. Xin cám ơn các bạn đã dành thời gian đọc và theo dõi. Peace!!!
Bình luận