#30daychallenge (16) | Valid Parenthesis String

  Valid Parenthesis String

Given a string containing only three types of characters: '(', ')' and '*', write a function to check whether this string is valid. We define the validity of a string by these rules:

1. Any left parenthesis '(' must have a corresponding right parenthesis ')'.
2. Any right parenthesis ')' must have a corresponding left parenthesis '('.
3. Left parenthesis '(' must go before the corresponding right parenthesis ')'.
4. '*' could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string.
5. An empty string is also valid.

Example 1:

Input: "()"
Output: True

Example 2:

Input: "(*)"
Output: True

Example 3:

Input: "(*))"
Output: True

Note:

1. The string size will be in the range [1, 100].

Cách làm thường thấy đối với bài này là quy hoạch động nhưng với O(N*N). Không những thế không gian cũng là N*N.

Cách thứ 2 là phương pháp tham lam. Gọi min là giá trị tối thiểu tại một thời điểm có bao nhiêu dấu ngoặc trái "(", gọi max là giá trị tối đa tại một thời điểm đếm xem có bao nhiêu dấu ngoặc trái "(".

Nếu max<0, tức không tồn tại một kết quả đúng tại thời điểm đó. Ví dụ : (*)))), ta có tập max: ]1 2 1 0 -1..] Đến -1 thì hoàn toàn không còn khả thi về chuyện đúng nữa rồi.

Còn Min, nó có thể âm, trong trường hợp này: ((**)))), ta có tập min: 1 2 2 2 1 0 -1 -2 -3, tập max: 1 2 3 4 3 2 1 0. Nếu thêm một dấu ngoặc phải nữa ")" thì điều kiện max > 0 sẽ không thỏa mãn, kết quả trả về false.

Giải thích thế thỏa mãn rồi, đây là code trên Java:


Hẹn gặp Leetcode vào ngày mai. Cảm ơn bạn !