一、題目
給你一個由 ‘('、')' 和小寫字母組成的字符串 s。
你需要從字符串中刪除最少數目的 ‘(' 或者 ‘)' （可以刪除任意位置的括號)，使得剩下的「括號字符串」有效。
有效「括號字符串」應當符合以下 任意一條 要求：
空字符串或只包含小寫字母的字符串
可以被寫作 AB（A 連接 B）的字符串，其中 A 和 B 都是有效「括號字符串」
可以被寫作 (A) 的字符串，其中 A 是一個有效的「括號字符串」
二、示例
|
1
2
3
4
5
6
7
8
9
10
|
))(( -》 (leetode -》 leetodeleetode) -》 leetode(lee(to)de -》 lee(to)delee(to)de) -》 lee(to)de(lee(t(c)o)de -》 lee(t(c)o)delee(t(c)o)de) -》 lee(t(c)o)de |
三、解法1
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
|
public class Test { public static void main(String[] args) { String s1 = "))(("; System.out.println(s1 + " -》 " + minRemoveToMakeValid(s1)); String s2 = "(leetode"; System.out.println(s2 + " -》 " + minRemoveToMakeValid(s2)); String s3 = "leetode)"; System.out.println(s3 + " -》 " + minRemoveToMakeValid(s3)); String s4 = "(lee(to)de"; System.out.println(s4 + " -》 " + minRemoveToMakeValid(s4)); String s5 = "lee(to)de)"; System.out.println(s5 + " -》 " + minRemoveToMakeValid(s5)); String s6 = "(lee(t(c)o)de"; System.out.println(s6 + " -》 " + minRemoveToMakeValid(s6)); String s7 = "lee(t(c)o)de)"; System.out.println(s7 + " -》 " + minRemoveToMakeValid(s7)); } public static String minRemoveToMakeValid(String str) { // 初始化"("和")"的個數為0 int left = 0; int right = 0; // 將字符串轉換為char數組 char[] chars = str.toCharArray(); // 從左到右標記多余的")"右括號 for (int i = 0; i < chars.length; i++) { if (chars[i] == '(') { left++; } else if (chars[i] == ')') { right++; } if (right > left) { chars[i] = '#'; left = right = 0; } } left = right = 0; // 從右到左標記多余的"("左括號 for (int i = chars.length - 1; i >= 0; i--) { if (chars[i] == '(') { left++; } else if (chars[i] == ')') { right++; } if (right < left) { chars[i] = '#'; left = right = 0; } } return String.valueOf(chars).replaceAll("#", ""); }} |
四、解法2
Stack.peek 與Sstack.pop 的區別
- 相同點：大家都返回棧頂的值。
- 不同點：peek 不改變棧的值(不刪除棧頂的值)，pop會把棧頂的值刪除。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
|
public class Test { public static void main(String[] args) { String s1 = "))(("; System.out.println(s1 + " -》 " + minRemoveToMakeValid(s1)); String s2 = "(leetode"; System.out.println(s2 + " -》 " + minRemoveToMakeValid(s2)); String s3 = "leetode)"; System.out.println(s3 + " -》 " + minRemoveToMakeValid(s3)); String s4 = "(lee(to)de"; System.out.println(s4 + " -》 " + minRemoveToMakeValid(s4)); String s5 = "lee(to)de)"; System.out.println(s5 + " -》 " + minRemoveToMakeValid(s5)); String s6 = "(lee(t(c)o)de"; System.out.println(s6 + " -》 " + minRemoveToMakeValid(s6)); String s7 = "lee(t(c)o)de)"; System.out.println(s7 + " -》 " + minRemoveToMakeValid(s7)); } public static String minRemoveToMakeValid(String str) { // 記錄要刪除括號的下標，然后從后往前刪除坐標 StringBuffer result = new StringBuffer(str); Stack<Integer> stack = new Stack<>(); ArrayList<Integer> deleteRes = new ArrayList<>(); for (int i = 0; i < str.length(); i++) { if (str.charAt(i) == '(') { stack.push(i); } else if (str.charAt(i) == ')') { if (stack.empty()) { deleteRes.add(i); } else if (str.charAt(stack.peek()) == '(') { stack.pop(); } } } while (!stack.empty()) { int temp = stack.peek(); stack.pop(); deleteRes.add(0, temp); } deleteRes.sort(Integer::compareTo); for (int i = deleteRes.size() - 1; i >= 0; i--) { result.deleteCharAt(deleteRes.get(i)); } return result.toString(); }} |
到此這篇關于Java移除無效括號的方法實現的文章就介紹到這了,更多相關Java移除無效括號內容請搜索服務器之家以前的文章或繼續瀏覽下面的相關文章希望大家以后多多支持服務器之家！
原文鏈接：https://xiaoer.blog.csdn.net/article/details/115921023
