算法-有效的括号

题目

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

• 左括号必须用相同类型的右括号闭合。
• 左括号必须以正确的顺序闭合。
   ##### 示例 1：

  输入：s = "()"
  输出：true

  示例 2：

  输入：s = "()[]{}"
  输出：true

  示例 3：

  输入：s = "(]"
  输出：false

  示例 4：

  输入：s = "([)]"
  输出：false

  示例 5：

  输入：s = "{[]}"
  输出：true

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解答

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    if(s.length % 2 != 0 ){//字符串长度是偶数
        return false;
    }
    let temp =[s.charAt(0)];//代比较数组
    let flag = true;
    for(let i =1;i<s.length ;i++){
        //括号都是成对出现的，当出现右括号时，
        //如果最后一位不是对应的左括号，则不匹配，需要退出循环，
        //如果匹配，退出最后一位
        //如果当前为左括号，则放入数组中
        switch(s.charAt(i)){
            case ')':
                temp.slice(-1) == '('?temp.pop():flag=false;
                break;
            case '}':
                temp.slice(-1) == '{'?temp.pop():flag=false;
                break;
            case ']':
                temp.slice(-1) == '['?temp.pop():flag=false;
                break;
            default:
                temp.push(s.charAt(i));
                break;
        }
        if(!flag){
            break;
        }
    }
    return !flag||temp.length>0?false:true;
};

复杂度分析

• 时间复杂度：O(n)，其中 n 是字符串 s 的长度。
• 空间复杂度：O(n)，最差情况为字符串全部为左括号。