leetcode -- 20. Valid Parentheses

本文主要是介绍leetcode -- 20. Valid Parentheses，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

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

An input string is valid if:

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
题目难度：Easy

AC代码1

常规解法

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

AC代码2

用 array 代替 stack

class Solution {public boolean isValid(String s) {char[] stack = new char[s.length()];int head = 0;for(char c : s.toCharArray()) {switch(c) {case '{':case '[':case '(':stack[head++] = c;break;case '}':if(head == 0 || stack[--head] != '{') return false;break;case ')':if(head == 0 || stack[--head] != '(') return false;break;case ']':if(head == 0 || stack[--head] != '[') return false;break;}}return head == 0;}
}