ValidParentheses之Java实现

一、题目

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

创新互联建站服务项目包括太仓网站建设、太仓网站制作、太仓网页制作以及太仓网络营销策划等。多年来，我们专注于互联网行业，利用自身积累的技术优势、行业经验、深度合作伙伴关系等，向广大中小型企业、政府机构等提供互联网行业的解决方案，太仓网站推广取得了明显的社会效益与经济效益。目前，我们服务的客户以成都为中心已经辐射到太仓省份的部分城市，未来相信会继续扩大服务区域并继续获得客户的支持与信任！

二、解题思路

1、利用List集合实现一个栈；
2、将字符串s转换成字符数组，并循环遍历；
3、如果字符为："{、(、["中的一个，则存入集合中；
4、如果字符为："}、)、]"中的一个，则取出集合中最后一个元素进行比较；
5、如能匹配上，则删除集合中最后一个元素，否则返回false；
6、最后判断集合大小是否为0，如是则返回true。

三、代码实现

public boolean isValid(String s) {
    if ("".equals(s)) {
        return true;
    } else {
        Map parentheseMap = new HashMap();
        parentheseMap.put(')', '(');
        parentheseMap.put(']', '[');
        parentheseMap.put('}', '{');        
        char[] sArr = s.toCharArray();
        List stackList = new ArrayList();
        for (int i = 0; i < sArr.length; i++) {
            if (sArr[i] == '(' || sArr[i] == '[' || sArr[i] == '{') {
                stackList.add(sArr[i]);
            } else {
                if (stackList.size() == 0) {
                    return false;
                } else {
                    char temp = stackList.get(stackList.size() - 1);
                    if (temp == parentheseMap.get(sArr[i])) {
                        stackList.remove(stackList.size() - 1);
                    } else {
                        return false;
                    }
                }
            }
        }
        return stackList.size() == 0 ? true : false;
    }
}

文章标题：ValidParentheses之Java实现
文章源于：http://mswzjz.cn/article/iidiho.html