Remove invalid parentheses
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Đề bài yêu cầu chúng mình loại bỏ số lượng dấu ngoặc tối thiểu để tạo ra một chuỗi hợp lệ.
Approach - BFS
( hoặc ), xóa nó đi và đưa vào hàng đợi (queue).Set<string> để lưu các chuỗi đã kiểm tra (visited)found = true), dừng quá trình kiểm tra thêm.1function removeInvalidParentheses(s: string): string[] {
2 function isValid(str: string): boolean {
3 let balance = 0;
4 for (const char of str) {
5 if (char === '(') {
6 balance++
7 } else if (char === ')') {
8 balance--;
9 if (balance < 0) {
10 return false
11 }
12 }
13 }
14 return balance === 0
15 }
16
17 const queue: string[] = [s];
18 const visited = new Set<string>([s]);
19 const result: string[] = [];
20 let found = false;
21
22 while (queue.length > 0) {
23 const size = queue.length;
24 for (let i = 0; i < size; i++) {
25 const current = queue.shift()!;
26 if (isValid(current)) {
27 result.push(current);
28 found = true
29 }
30
31 if (found) {
32 continue
33 }
34
35 for (let j = 0; j < current.length; j++) {
36 if (current[j] !== '(' && current[j] !== ")") continue
37 const newStr = current.slice(0, j) + current.slice(j + 1);
38 if (!visited.has(newStr)) {
39 queue.push(newStr)
40 visited.add(newStr)
41 }
42 }
43
44 }
45 if (found) {
46 break;
47 }
48 }
49
50 return result;
51};