20.有效的括号

题目描述

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

有效字符串需满足：

1.左括号必须用相同类型的右括号闭合。
2.左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

示例1:

输入: "()"
输出: true

示例2:

输入: "(]"
输出: false

思路

1.判断括号匹配很符合栈的特点，所以我们可以用栈来实现。
2.我们可以用哈希表来存储一组括号，将右括号作为键值，因为我们要通过右括号判断是否取出栈顶元素。
3.最后注意处理栈空的情况就可以了。

Java代码实现

  public boolean isValid(String s) {
        Map<String,String> bracketsMap = new HashMap<String,String>();
        bracketsMap.put(")","(");
        bracketsMap.put("]","[");
        bracketsMap.put("}","{");

        Stack<String> bracketsStack = new Stack<>();

        for (int i = 0; i < s.length(); i++) {
            String cur = s.substring(i,i+1);
            //判断是否为右括号系列
            if(bracketsMap.containsKey(cur)){
                //若要压入的值为右括号，且栈为空，那一定无法匹配
                if(bracketsStack.empty())
                    return false;
                else {
                    //判断括号是否匹配
                    if(bracketsMap.get(cur).equals(bracketsStack.peek())){
                        bracketsStack.pop();
                    }else {
                        bracketsStack.push(cur);
                    }
                }
            }else {
                bracketsStack.push(cur);
            }
        }

        return bracketsStack.empty();
    }

Golang代码实现

func isValid(s string) bool {
    stack := list.New()
    paramMap := map[string]string{
        ")":"(",
        "}":"{",
        "]":"[",
    }
    for i:=0; i<len(s); i++ {
        if stack.Len() == 0 {
            stack.PushBack(s[i:i+1])
        }else{
            cur := s[i:i+1]
            top := stack.Back()
            if paramMap[cur] == top.Value {
                stack.Remove(top)
            }else{
                stack.PushBack(cur)
            }
        }
    }
    return stack.Len() == 0;
}