GuilinDev

Lc0921

05 August 2008

921 Minimum Add to Make Parentheses Valid

使括号字符串有效的最小添加数 - 计数平衡

分析

用栈的方式, 剩在栈里的, 都是需要添加的

用计数方式, 配不上对儿的 , 左右括号

计数模拟栈： O(n) + o(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
    public int minAddToMakeValid(String s) {
		int left = 0;
		int ans = 0;
		for (char c : s.toCharArray()) {
			if (c == '(') {
				left++; 
			} else if (c == ')' && left > 0) {
				left--;
			} else {
				ans++; // 无处安放的 ')'
			}
		}
		return ans + left; // 无家可归的'(' 和 无处安放的 ')'
	}
}

用栈

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution {
	public int minAddToMakeValid(String s) {
		Stack<Character> stack = new Stack<>();
		for (char c : s.toCharArray()) {
			if (c == ')' && !stack.isEmpty() && stack.peek() == '(') {
				stack.pop();
			} else {
				stack.add(c);
			}
		}
		return stack.size();
	}
}
This site is open source. Improve this page.