leetcode-java-20-有效的括号(valid parentheses)-java

题目及测试

package pid020;
/* 有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：

    左括号必须用相同类型的右括号闭合。
    左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

示例 1:

输入: "()"
输出: true

示例 2:

输入: "()[]{}"
输出: true

示例 3:

输入: "(]"
输出: false

示例 4:

输入: "([)]"
输出: false

示例 5:

输入: "{[]}"
输出: true


}*/
public class main {
	
	public static void main(String[] args) {
		String[] testTable = {"()","()[]{}","(]","([)]","{[]}"};
		for (String ito : testTable) {
			test(ito);
		}
	}
		 
	private static void test(String ito) {
		Solution solution = new Solution();
		boolean rtn;
		long begin = System.currentTimeMillis();
		
		    System.out.print(ito+" ");
		rtn = solution.isValid(ito);//执行程序
		long end = System.currentTimeMillis();		
		System.out.println("rtn=" + rtn);
		
		System.out.println();
		System.out.println("耗时：" + (end - begin) + "ms");
		System.out.println("-------------------");
	}

}

解法1（成功，13ms，较慢）
用栈，如果是前面的括号则直接入栈，如果是后面的先检查栈是否为空，然后看pop出的括号是否为对应的前括号，最后遍历完检查栈是否为空，若不为空，这说明有前扩或未对应

package pid020;

import java.util.Stack;

public class Solution {
public boolean isValid(String s) {
    Stack<Character> stack=new Stack<>();
    Character now;
    Character prev;
    int length=s.length();
    for(int i=0;i<length;i++){
    	now=s.charAt(i);
    	if(now=='('||now=='['||now=='{'){
    		stack.push(now);
    	}
    	else{
			if(stack.isEmpty()){
				return false;
			}else{
				prev=stack.pop();
			}
			
    		if(now==')'){   			
    			if(prev!='('){
    				return false;
    			}
    		}
    		else if(now==']'){
    			if(prev!='['){
    				return false;
    			}
    		}
    		else if(now=='}'){
    			if(prev!='{'){
    				return false;
    			}
    		}
    	}
    }
	if(stack.isEmpty()){
		return true;
	}
	else{
		return false;
	}
    }

}

解法2（别人的）
内容一样，用switch和各种方法简化了流程

public boolean isValid(String s) {
 Stack<Character> stack = new Stack<Character>(); 
 for (int i = 0; i < s.length(); ++ i) { 
 switch (s.charAt(i)) { 
 case ')': 
 if (stack.isEmpty() || !stack.pop().equals('(')) 
 return false; 
 break; 
 case ']': 
 if (stack.isEmpty() || !stack.pop().equals('[')) 
 return false; 
 break; 
 case '}':
  if (stack.isEmpty() || !stack.pop().equals('{'))
   return false;
    break;
     default: 
     stack.push(s.charAt(i)); break; } } 
     return stack.isEmpty(); }

解法3（别人的）
用map的方式进行简化和对应

public class Solution { public boolean isValid(String s) { Map<Character,Character> map = new HashMap<>(); map.put('(', ')'); map.put('[', ']'); map.put('{', '}'); Stack<Character> stack = new Stack<>(); for(int i=0;i<s.length();i++) { char curr = s.charAt(i); if(map.keySet().contains(curr)) { stack.push(curr); } else { if(!stack.empty() && map.get(stack.peek()) == curr) { stack.pop(); } else { return false; } } } return stack.empty(); } }