LeetCode 每日一题 [6] 有效的括号

LeetCode 有效的括号 [简单]

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-parentheses

示例 1:

输入: "()"
输出: true

示例 2:

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

示例 3:

输入: "(]"
输出: false

示例 4:

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

示例 5:

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

题目分析

方法1:

这个题目很明显，很符合栈的先进先出的特点，所以使用栈来实现，那么在栈进行保存的时候，可以选择保存左边的部分括号，也可以保存右边的括号，如果是保存左边的括号，需要能够判断如果是左边的括号，那么右边的对应的括号能不能找得到，所以这里使用一个HashMap来进行存储

方法2：

不使用HashMap实现，在进栈的时候，直接存储对应的另外一半，如果不能匹配左边的，就需要出栈进行匹配右边的，如果也不能匹配，那么就不符合，直接跳出。，最后判断栈是否为空，如果不为空，那么就多余了一个，此时这个判断我在进入方法的时候就判断了，也就是，如果字符串的个数为奇数，那么就一定不符合条件，那么最后一步可以使用 return true; 代替 stack.isEmpty(); 但是如果是 "(("那就错了，所以还是需要使用 stack.isEmpty()

代码实现

public class LeetCode_06_ValidParentheses {

    private static final Map<Character, Character> map = new HashMap<Character, Character>();

    static {
        map.put('(', ')');
        map.put('{', '}');
        map.put('[', ']');
        map.put('?', '?');
    }

    public static void main(String[] args) {

        String target = "((";
        boolean valid02 = isValid02(target);
        System.out.println(valid02);
    }

    public static boolean isValid03(String s) {
        if (s == null || s.length() % 2 != 0) {
            return false;
        }
        Stack<Character> stack = new Stack<>();
        for (Character c : s.toCharArray()) {

            switch (c) {
                case '(':
                    stack.push(')');
                    break;
                case '[':
                    stack.push(']');
                    break;
                case '{':
                    stack.push('}');
                    break;
                default:
                    if (!stack.isEmpty() && !c.equals(stack.pop())) {
                        return false;
                    }
            }
        }
        return stack.isEmpty();
    }

    public static boolean isValid02(String s) {
        if (s == null || s.length() % 2 != 0) {
            return false;
        }
        Stack<Character> stack = new Stack<>();
        for (Character c : s.toCharArray()) {
            if (c.equals('(')) {
                stack.push(')');
            } else if (c.equals('[')) {
                stack.push(']');
            } else if (c.equals('{')) {
                stack.push('}');
            } else if (!stack.isEmpty() && !c.equals(stack.pop())) {
                return false;
            }
        }
        //return true;
        return stack.isEmpty();
    }


    public static boolean isValid(String s) {

        if (s == null || s.length() == 0 || s.length() % 2 != 0 || !map.containsKey(s.charAt(0))) {
            return false;
        }
        LinkedList<Character> stack = new LinkedList<>();
        stack.add('?');
        for (Character c : s.toCharArray()) {
            if (map.containsKey(c)) {
                stack.addLast(c);
            } else if (!map.get(stack.removeLast()).equals(c)) {
                return false;
            }
        }
        return stack.size() == 1;
    }
}