LeetCode 20. Valid Parentheses

佚名 6年前 (2018-10-13) 算法 1047人围观抢沙发百度已收录

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.

Note that an empty string is also considered valid.

Example 1:

Input: "()"

Output: true

Example 2:

Input: "()[]{}"

Output: true

Example 3:

Input: "(]"

Output: false

Example 4:

Input: "([)]"

Output: false

Example 5:

Input: "{[]}"

Output: true

package LeetCode;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class L20_ValidParentheses {
    public boolean isValid(String s) {
        int len=s.length();
        Stack<Character> stack=new Stack<Character>();
        if(len==0)
            return true;
        if(len%2!=0)
            return false;
        Map<Character,Character> map=new HashMap<Character,Character>();
        map.put('(',')');
        map.put('[',']');
        map.put('{','}');
        map.put(')',' ');
        map.put(']',' ');
        map.put('}',' ');
        //stack.push(s.charAt(0));
        for(int i=0;i<len;i++)
        {
            if (stack.empty())//栈为空
                stack.push(s.charAt(i));
            else if(s.charAt(i)!=map.get(stack.peek()))//或输入与栈顶不匹配
                stack.push(s.charAt(i));
            else
                stack.pop();
        }
        if(stack.empty())
            return true;
        else
            return false;
    }

    public static void main(String[] args){
        L20_ValidParentheses l20=new L20_ValidParentheses();
        String test="([)]";
        boolean result=l20.isValid(test);
        System.out.println(result);
    }
}