LeetCode20. Valid Parentheses

发表于 | 分类于 |

思路构思

针对这个题目，先想几组input进行分析

输入input

  • (())

    在从左到右遍历过程中input[0]在遍历到它时，无法知道它会和后面哪一个括号匹配
    因此需要把它先保存起来，但是如果存在一个右括号，它的匹配顺序又会是自右向左匹配的

    因此可以得出结论，可以凭借栈来完成这项要求

  • ()()

    针对这种匹配情况，上述思路也能满足

代码

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
public boolean isValid(String s) {
        
        if(s == null || s.length() == 0) return true;
        
		int len = s.length();
		Stack<Character> stack = new Stack<>();
		Set<Character> frontSet = new HashSet<>();
		Set<Character> endSet = new HashSet<>();
		frontSet.add('(');
		frontSet.add('[');
		frontSet.add('{');
		for(int i = 0; i < len; i++) {
			Character c = s.charAt(i);
			if(frontSet.contains(c)) {
				stack.push(c);
			}else {
				if(stack.isEmpty()) return false;
				Character t = stack.pop();
				if(c == ')' && t != '(') {
					return false;
				}else if(c == ']' && t != '[') {
					return false;
				}else if(c == '}' && t != '{') {
					return false;
				}
			}
		}
		if(!stack.isEmpty()) return false;
		return true;
	}