Leetcode bài 32 - Longest Valid Parentheses
Link: https://leetcode.com/problems/longest-valid-parentheses/
Bài này là bài khó, hiện tại mình vẫn chưa có cách nào để giải dù là vét cạn hay là làm thuật toán.
Đề yêu cầu:
Cho một chuỗi dấu ngoặc đóng mở bất kỳ, trả về độ dài chuỗi đóng mở có nghĩa lớn nhất.
Ví dụ:
1. Chuỗi "(()" trả về 2 với "()" là chuỗi có nghĩa.
2. Chuỗi ")()())" trả về 4 với "()()" là chuỗi có nghĩa lớn nhất.
3. Chuỗi "()(()" trả về 2. Hai chuỗi thoả mãn đều là "()" và độ dài như nhau.
3*. Chuỗi "" trả về 0.
Lần đầu tiên mình làm thế này.
- Tạo một biến đếm int là 'sump'. Nếu gặp dấu mở ngoặc thì tăng lên 1 còn nếu gặp dấu đóng ngoặc thì nó giảm đi 1.
- Tạo thêm biến count để đếm số lầm sump giảm đi, vì nếu sump dương tức là còn mở ngoặc mà đóng ngoặc thì count vẫn đếm cho đến khi nào sump xuống dưới 0 thì thôi.
- Khi sump xuống dưới 0 thì tự động reset hai giá trị về 0 vì dấu đóng ngoặc trước dấu mở ngoặc thì không có nghĩa.
* Trong mỗi chặng lấy giá trị lớn nhất của count. Riêng chặng cuối cần lấy count - sum để bỏ đi phần ngoặc mở còn thừa lại ra chuỗi có độ dài hợp lý nhất.
Code:
int sump = 0;
int counter = 0;
int ans = 0;
for (std::size_t idx{0}; idx < s.length(); ++idx) {
if(s[idx] == '(') {
++sump;
++counter;
} else { // s[idx] == ')'
if(--sump >= 0)++counter;
}
if(sump < 0) {
ans = max(ans, counter);
counter = 0;
sump = 0;
}
printf("Check \'%c\' counter: %d, sump: %d, ans : %d\n", s[idx], counter, sump, ans);
}
ans = max(ans, counter-sump);
return ans;
}
II Test
Để test bài này thì mình dùng struct test và cả hàm test như sau:
std::string str;
int ans;
TesCase(std::string s, int v) : str(s), ans(v) {};
};
void DoTest(std::vector<TesCase> test_case) {
for(TesCase T : test_case) {
int ans = longestValidParentheses(T.str);
if(ans == T.ans) {
printf("[O] PASS\n");
} else {
printf("[X] FALSE -> ans: %d, expect: %d\n", ans, T.ans);
}
}
}
int main()
{
std::vector<TesCase> test_case;
test_case.push_back(TesCase("(()", 2));
test_case.push_back(TesCase(")()())", 4));
test_case.push_back(TesCase("", 0));
test_case.push_back(TesCase("))((())()())", 10));
test_case.push_back(TesCase("()(()", 2));
test_case.push_back(TesCase("()(((()(()))", 10));
DoTest(test_case);
return EXIT_SUCCESS;
}
Kết quả trả về báo cáo sai testcase "()(()". Lúc này chương trình trả về kết quả là 4 với mong muốn là 2. Tại vì lỗi logic tiếp tục đếm khi mà gặp dấu mở ngoặc. Liệu mấy hôm nữa mình có giải tiếp được bài này không hay phải chuyển bài khác?
Nhận xét
Đăng nhận xét