Valid Parentheses

Leave a comment

November 2, 2016 by oneOokay

注意一下corner case:

  1. [[]:当string扫完之后stack不为空
  2. []]]:扫string的过程中stack已经为空了

Nov2

疑惑了一下不知道要考什么,后来应该是character的顺序吧。

我用了一个for-loop, stack和hashmap来完成:结果发现哈哈哈想的挺靠近不容易啊。

总体思想就是:遇到左括号就应该往stack里面放,遇到右括号,peek stack,如果为相应的左括号则pop,如果不是那么return false。到最后stack如果为空,return true,不空的话return false。然后对于如何判定括号是否对应有自己的技巧吧。我用了hashmap,应该有其他的方法,我这个的hashmap的查找可能要多一点时间吧,不清楚。(Hashmap: search average time complexity O(1))

  • 一个String:”[]{}()”, stack里头放index,用indexof来通过index判断
  • 或者用switch, 不存括号,这个好像更好

相关method:

  • String str = Character.toString(str.charAt(i));
  • char[] chars = str.toCharArray();
public class Solution {
 public boolean isValid(String s) {
 if (s == null || s.length() <= 1){
 return false;
 }
 Stack<Character> stack = new Stack<Character>();
 HashMap<Character, Character> map = new HashMap<Character, Character>();
 map.put(')', '(');
 map.put('}','{');
 map.put(']','[');
 
 for (int i = 0; i < s.length(); i ++){
 if (!map.containsKey(s.charAt(i))){
 stack.push(s.charAt(i));
 }else {
 if (stack.isEmpty() || stack.peek() != map.get(s.charAt(i))){
 return false;
 }
 stack.pop();
 }
 }
 return stack.isEmpty();
 }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: