LeetCode - Algorithms - 20. Valid Parentheses

Difficulty:Easy的题，在面试现场，面对黑板，我毫无头绪没有任何思路，考官已经提示自己你想想有什么数据结构可以利用，自己还是没想通。

This is a problem that’s good to use a stack.

回来上网找线索，主要参考了这个20 LeetCode Java: Valid Parentheses – Easy，此题的关键确实就是数据结构，要用Stack（栈），其实在做表达式解析那两道题227. Basic Calculator II、224. Basic Calculator时已经碰到过，自己也做了题，但还是没理解透，遇到新问题又傻眼了。

代码是人家的，天下程序一大抄！！！但不理解的话，代码不会内化于你。看来自己做LeetCode算法题凑数没用，理解不深，做完了又忘了。看来做完了还得温故知新加深理解。

Java

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
class Solution {
    public boolean isValid(String s) {
    	HashMap<Character, Character> pair = new HashMap<Character, Character>();
        pair.put(')','(');
        pair.put('}','{');
        pair.put(']','[');    	
        Stack<Character> stk = new Stack<Character>();
        char c = '\u0000';
        for(int i=0;i<s.length();i++) {
        	c = s.charAt(i);
        	switch(c) {
        	case '{':
        	case '[':
        	case '(':
        		stk.push(c);
        		break;
        	default:
        		if (stk.isEmpty() || pair.get(c)!=stk.pop())
        			return false;
        	}
        }
        if (stk.isEmpty())
        	return true;
        return false;        
    }
}

Submission Detail

  • 76 / 76 test cases passed.
  • Runtime: 5 ms
  • Your runtime beats 98.09 % of java submissions.

JavaScript

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
/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
	var pair = {'\}':'\{','\]':'\[',')':'('};
	var stk = new Array();
	var c = '';
	for(var i=0;i<s.length;i++) {
		c = s[i];
		switch(c) {
		case '{':
		case '[':
		case '(':
			stk.push(c);
		    break;
		default:
			if (stk.length==0 || pair[c]!=stk.pop()) {
				return false;
			}
		}
	}
	if (stk.length==0) return true;
	return false;    
};

Submission Detail

  • 76 / 76 test cases passed.
  • Runtime: 52 ms
  • Your runtime beats 100.00 % of javascript submissions.