[Vietnamese] A valid parenthesis string (JavaScript implement)
Chào mọi người, trong bài viết đầu tiên sau Tết 2023, mình muốn bắt đầu bằng một cái gì nó nhẹ nhàng nên quyết định chọn một bài toán tin đã làm khó mình trong khoảng thời gian lúc trước khi đi phỏng vấn để mổ xẻ về thuật toán và cách mình suy nghĩ.
Hầu hết các bài phỏng vấn về thuật toán chúng ta đều có thể tìm được ở trên mạng (khoảng 80, 90%), và bài dưới đây cũng không phải ngoại lệ:
Question: Given a string s containing only three types of characters: '(', ')' and '*', return true if s is valid.
The following rules define a valid string:
Any left parenthesis
'('must have a corresponding right parenthesis')'.Any right parenthesis
')'must have a corresponding left parenthesis'('.Left parenthesis
'('must go before the corresponding right parenthesis')'.'*'could be treated as a single right parenthesis')'or a single left parenthesis'('or an empty string"".
Nếu bạn nào làm thuật toán nhiều chắc chắn sẽ nhận ra ngay dạng bài có cặp ngoặc đóng mở này là dùng cấu trúc dữ liệu Stack. Tuy nhiên, ngoài hai dấu ( và ) thì đề bài này chúng ta còn có dấu * tại vị trí i có thể nhận một trong hai giá trị là ( hoặc ). Như vậy, có vẻ độ khó đã được tăng lên so với việc chuỗi của chúng ta chỉ có ( và ).
Còn nếu bạn nào chưa biết việc dùng stack để giải như thế nào thì mình có thể tóm tắt như sau (trường hợp chưa có dấu *). Chúng ta sẽ duyệt từ đầu đến cuối chuỗi, nếu gặp dấu ( mình sẽ bỏ vào stack, ngược lại nếu gặp dấu ) mình sẽ pop phần tử trên cùng ra khỏi stack. Kết thúc quá trình, nếu stack của mình là rỗng thì chuỗi đã cho là một valid parenthesis, ngược lại là invalid.
function validParenthesis (str) {
if (str.length === 0 || str.length === 1) return false;
let myStack = [];
for (let i = 0; i < str.length; i++) {
if (str[i] === '(') myStack.push('(');
else {
if (myStack.length === 0) return false;
myStack.pop();
}
}
return myStack.length === 0;
}
Trong hàm validParenthesis mình sử dụng một mảng để minh họa cho stack với hai thao tác push() - thêm một phần tử mới vào stack (ở đây là thêm phần tử mới vào cuối mảng) và pop() - lấy phần tử trên cùng của stack ra (ở đây là bỏ phần tử đầu tiên của mảng). Như vậy, sau khi kết thúc vòng lặp, nếu mảng rỗng nghĩa là stack của mình đã rỗng và ngược lại.
Trở lại bài toán ban đầu. Việc xuất hiện thêm dấu * có thể được giải quyết một cách trâu bò (brute force) như sau:
Với mỗi dấu *, mình sẽ có 3 cách thay thế nó thành (, ) hoặc '' . Như vậy, từ một chuỗi có n dấu * ban đầu, mình sẽ có được bao nhiêu chuỗi mới mất đi dấu *? Câu trả lời sẽ là 3^n! Một con số khó có thể chấp nhận được. Tuy nhiên, đây cũng là một cách làm. Sau khi mình liệt kê tất cả cấu hình, thì mình sẽ duyệt qua 3^n cấu hình này và dùng hàm validParenthesis để kiểm tra. Dễ thấy độ phức tạp của thuật toán là ...3^n * n . Tuy nhiên cũng cần lưu ý rằng, n ở đây mình đang đề cập là số dấu * trong chuỗi ban đầu. Nên nếu con số này nhỏ thì thuật toán này cũng chấp nhận được.
Một dữ kiện mà mình chưa đưa vào ở trên là:
- The string size will be in the range [1, 100].
Như vậy, với dữ kiện này thì nếu n = 100 thuật toán brute ở trên sẽ không hoạt động tốt nhưng nếu một thuạt toán có thời gian đa thức thì chúng ta sẽ chấp nhận được. Nếu bạn thích, bạn có thể dừng tại đây để tìm kiếm một lời giải có thời gian đa thức như mình nói. Và lưu ý rằng, thời gian đa thức không nhất thiết phải là O(n), nó cũng có thể là O(n^2), O(n^3)...Tất nhiên bậc của đa thức càng nhỏ càng tốt! Cụ thể hơn, mọi người có thể xem lại ở đây: https://en.wikipedia.org/wiki/Time_complexity#Polynomial_time
Bây giờ, mình muốn giới thiệu với mọi người một lời giải bằng phương pháp Quy hoạch động (Dynamic Programming) cho bài toán này. Trước tiên, mình thử vẽ ra một ví dụ để dễ minh họa cho ý tưởng quy hoạch động, hay nói cách khác là chia nhỏ một bài toán lớn thành các bài toán con.
Có khá nhiều tài liệu và bài viết nói về quy hoạch động, nhưng nếu chỉ dừng lại ở việc đề cập là chia nhỏ bài toán lớn thành các bài toán con thì mình thấy chưa đầy đủ. Chia như thế nào? Một ví dụ người ta thường dùng là dãy Fibonacci thì bản thân bài toán đã có sẵn công thức truy hồi, còn nếu gặp bài khác thì sao?
Nói cách khác, việc tìm ra quan hệ giữ F(i) và F(i - 1), F(i - 2)... là vấn đề cần được giải quyết đầu tiên trong phương pháp quy hoạch động. Khi đã tìm ra, công việc còn lại của chúng ta sẽ dễ thở hơn (trong đa số trường hợp). Thông thường, việc chia một bài toán lớn thành hai hoặc nhiều bài toán con sẽ xảy ra ở các đầu biên (nếu ta lấy hoặc không lấy phần tử ở một hoặc hai đầu biên). Cũng có nhiều trường hợp việc chia nhỏ xảy ra tất cả mọi nơi và mình phải tìm cực trị. Những bài toán này thường có độ khó cao hơn và mình cũng chưa đủ thời gian tìm hiểu hết, hẹn mọi người trong một bài khác.
Quay lại bài này, mình có thể chia bài toán ban đầu bằng các vị trí ở 2 biên được. Giả sử A là một chuỗi ngoặc đúng (valid parenthesis) thì khi đó B sẽ đúng nếu: