678. Valid Parenthesis String
Tags:
Medium
Skills:
StringGreedy
June 24, 2025
04:33 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Cho một chuỗi chỉ gồm các ký tự '(', ')', và '*'. Ký tự '*' có thể được coi như '(', ')' hoặc là chuỗi rỗng. Hãy xác định xem có thể thay thế các ký tự '*' để chuỗi trở thành một chuỗi dấu ngoặc hợp lệ khôn
Approach
Bài này có thể giải bằng phương pháp greedy với hai biến theo dõi biên dưới và biên trên số lượng ngoặc mở hợp lệ có thể có tại mỗi thời điểm:
'*' là ')' hoặc rỗng).'*' là '(').Duyệt từ trái sang phải
'(': tăng cả low và high.')': giảm cả low và high.'*': giảm low (nếu > 0), tăng high.Nếu tại bất kỳ thời điểm nào high < 0 thì return false (có quá nhiều dấu đóng không thể cân bằng)
Kết thúc duyệt, nếu low === 0 thì chuỗi hợp lệ, ngược lại là không hợp lệ
Time and space complexity
Solution
1function checkValidString(s: string): boolean {
2 let low = 0
3 let high = 0
4 for (const c of s) {
5 if (c === '(') {
6 low++
7 high++
8 } else if (c === ')') {
9 if (low > 0) low--;
10 high--
11 } else {
12 if (low > 0) low--
13 high++
14 }
15 if (high < 0) return false // too many )
16 }function checkValidString(s: string): boolean {
17 let low = 0
18 let high = 0
19 for (const c of s) {
20 if (c === '(') {
21 low++
22 high++
23 } else if (c === ')') {
24 if (low > 0) low--;
25 high--
26 } else {
27 if (low > 0) low--
28 high++
29 }
30 if (high < 0) return false // too many )
31 }
32 return low === 0
33};
34
35/**
36low đại diện cho số lượng ( trong trường hợp nhỏ nhất
37high đại diện cho số lượng ( trong trường hợp lớn nhất -> lớn nhất rồi thì không
38
39 */
40 return low === 0
41};