博客

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。

左括号必须以正确的顺序闭合。

1、括号成对，字符个数单数肯定不符合。

2、

遇见左括号（”(“,”[“,”{“）入栈，遇见右括号 “)”,”]”,”}”）出栈开始配对

，栈内不可能存在右括号，如果栈内存在右括号一定匹配失败

3、利用map维护右括号与左括号的成对映射，当然不使用map也可以

public class Solution {
    public static boolean isValid(String s) {
        if(s.length()%2!=0)
        {
            return false;
        }
        Stack<Character> stack = new Stack();
        Map<Character,Character> map = new HashMap();
        map.put(')','(');
        map.put(']','[');
        map.put('}','{');
        for(int i=0;i<s.length();i++)
        {
            char ch=s.charAt(i);
//左括号入栈
            if(map.containsValue(ch))
            {
                stack.push(ch);
            }
//右括号  栈不为空并且也不成对
            else if(stack.isEmpty()||!map.get(ch).equals(stack.pop()))
            {
                    return false;
            }
        }
//匹配之后栈内是否还有多的左括号
        if(stack.size()==0)
            return true;
        else
            return false;
    }
    }