力扣20有效的括号题解

1.题目
给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串，判断字符串是否有效。
有效字符串需满足：

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

注意空字符串可被认为是有效字符串。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-parentheses
2.想法
先创建一个动态数组作为栈，java中用ArrayList，将所给字符串转化为字符数组，循环遍历该数组，将左括号类型的放入动态数组，若遇到右括号则将对应的左括号从动态数组中删除，最终若动态数组的元素为空则为有效括号返回true，反之亦然。
3.图解
来源：力扣（LeetCode）官方题解
4.注意点
（1）有可能出现单右括号的例子
5.自己题解

class Solution {
    public boolean isValid(String s) {
       char []a=s.toCharArray();
       ArrayList b=new ArrayList();
 for(int i=0;i<a.length;i++)
{
if(a[i]=='('||a[i]=='['||a[i]=='{'){b.add(a[i]);}
else if(a[i]==')'){
  int p=b.lastIndexOf('(');
  if(p==b.size()-1&&b.size()!=0){b.remove(p);}
  else{return false;}}
else if(a[i]==']'){
  int p=b.lastIndexOf('[');
  if(p==b.size()-1&&b.size()!=0){b.remove(p);}
  else{return false;}}
else if(a[i]=='}'){ 
  int p=b.lastIndexOf('{');
  if(p==b.size()-1&&b.size()!=0){b.remove(p);}
  else{return false;}}
 } 
if(b.size()!=0){return false;}
       return true; 
       }
    }

6.知识点
（1）利用栈解决匹配问题
（2）java有自带的Stack类作为栈
7.官方题解

class Solution {

  // Hash table that takes care of the mappings.
  private HashMap<Character, Character> mappings;

  // Initialize hash map with mappings. This simply makes the code easier to read.
  public Solution() {
    this.mappings = new HashMap<Character, Character>();
    this.mappings.put(')', '(');
    this.mappings.put('}', '{');
    this.mappings.put(']', '[');
  }

  public boolean isValid(String s) {

    // Initialize a stack to be used in the algorithm.
    Stack<Character> stack = new Stack<Character>();

    for (int i = 0; i < s.length(); i++) {
      char c = s.charAt(i);

      // If the current character is a closing bracket.
      if (this.mappings.containsKey(c)) {

        // Get the top element of the stack. If the stack is empty, set a dummy value of '#'
        char topElement = stack.empty() ? '#' : stack.pop();

        // If the mapping for this bracket doesn't match the stack's top element, return false.
        if (topElement != this.mappings.get(c)) {
          return false;
        }
      } else {
        // If it was an opening bracket, push to the stack.
        stack.push(c);
      }
    }

    // If the stack still contains elements, then it is an invalid expression.
    return stack.isEmpty();
  }
}

作者：LeetCode
链接：https://leetcode-cn.com/problems/valid-parentheses/solution/you-xiao-de-gua-hao-by-leetcode/
来源：力扣（LeetCode）