1、题目名称

Valid Parentheses（合理的括号搭配）

2、题目地址

3、题目内容

英文：Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

中文：给定一个仅包含六种括号的字符串，判断这个字符串中的括号是否按正确的顺序排列。六种括号包括小括号 ( )、中括号 [ ]、大括号 { }

4、解题方法1

一种方式是使用链表记录遇到过的括号，每次找到反括号的时候，检查最后添加的括号是否与当前找到的反括号匹配。

Java代码如下：

import java.util.LinkedList;/** * @功能说明：LeetCode 20 - Valid Parentheses * @开发人员：Tsybius2014 * @开发时间：2015年11月8日 */public class Solution {        /**     * 合理的括号组合     * @param s     * @return     */    public boolean isValid(String s) {               LinkedList
    
      linkedList = new LinkedList
     
      ();                for (char ch : s.toCharArray()) {            if (ch == '(' || ch == '[' || ch == '{') {                linkedList.add(ch);            } else if (ch == ')') {                if (linkedList.isEmpty() || linkedList.getLast() != '(') {                    return false;                } else {                    linkedList.removeLast();                }            } else if (ch == ']') {                if (linkedList.isEmpty() || linkedList.getLast() != '[') {                    return false;                } else {                    linkedList.removeLast();                }            } else if (ch == '}') {                if (linkedList.isEmpty() || linkedList.getLast() != '{') {                    return false;                } else {                    linkedList.removeLast();                }            } else {                return false;            }        }                return linkedList.isEmpty();    }}
     
    

另一种方式是使用栈（Stack）来处理，方式和上一种用链表的方式相似：

import java.util.Stack;/** * @功能说明：LeetCode 20 - Valid Parentheses * @开发人员：Tsybius2014 * @开发时间：2015年11月8日 */public class Solution {        /**     * 合理的括号组合     * @param s     * @return     */    public boolean isValid(String s) {               Stack
    
      stack = new Stack
     
      ();                for (char ch : s.toCharArray()) {            if (ch == '(') {                stack.push(')');            } else if (ch == '[') {                stack.push(']');            } else if (ch == '{') {                stack.push('}');            } else if (stack.isEmpty() || stack.pop() != ch) {                return false;            }        }                return stack.isEmpty();    }}
     
    

5、解题方法2

看了讨论区后还发现了另一种解题方法，即使用String类下面的replace方法，不断消除掉相邻的正反括号，最后无法消除时，查看字符串内是否还有残留字符。这种方法实现起来比较简单，但效率比上面写的两种方法低很多。

Java代码如下：

/** * @功能说明：LeetCode 20 - Valid Parentheses * @开发人员：Tsybius2014 * @开发时间：2015年11月8日 */public class Solution {        /**     * 合理的括号组合     * @param s     * @return     */    public boolean isValid(String s) {               int length = s.length();        String stemp;        do {            stemp = s;            s = s.replace("()", "");            s = s.replace("[]", "");            s = s.replace("{}", "");            length = s.length();        } while (length == s.length() && !stemp.equals(s));                return length == 0;    }}

END