leetcode20-有效括号

题目

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

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

输入示例以及提示

示例 1：

**输入：**s = “()”

**输出：**true

示例 2：

**输入：**s = “()[]{}”

**输出：**true

示例 3：

**输入：**s = “(]”

**输出：**false

示例 4：

**输入：**s = “([])”

**输出：**true

示例 5：

**输入：**s = “([)]”

**输出：**false

提示：

• 1 <= s.length <= 10<sup>4</sup>
• s 仅由括号 '()[]{}' 组成

思考

方案一（错误）

我们首先的想法是拿出来 所有的左括号，再拿出所有的右括号 ，放入对应的数组，如果左侧括号和右侧括号两个数组的长度相等，则括号对应

let s= '([)]';//"()[]{}";
		console.log(s,'s');
		function isvalidkuohao(str){
			let arrA=[],arrB=[];
			for (let  i = 0; i < str.length; i++) {
				console.log(str[i],'iiii');
				if(str[i]=='('||str[i]=='{'||str[i]=='['){
					arrA.push(str[i])	
				}else if(str[i]==')'||str[i]=='}'||str[i]==']'){
					arrB.push(str[i])
				}else{}
			}
			if(arrA.length==arrB.length){
				console.log('true');
				return true;
			}else{
				console.log('false');
				return false;
			}
		}
isvalidkuohao(s);

但是很明显我们这种参数的结果是错误的'([)]',所以我们调整，应该对应我们下边

比如：左侧最后一个对应右侧第一个是正确的闭合

方案二 （ok）

换个思考，其实就是我们从左侧拿出来的和右边的形成对称

也就是左边最后一个应该是右边第一个 对比有效闭合的

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function (str) {
    const stack = [];
    for (let i = 0; i < str.length; i++) {
        const char = str[i];
        if (char === '(' || char === '{' || char === '[') {
            // 如果是左括号，压入栈中
            stack.push(char);
        } else {
            // 如果是右括号
            if (stack.length === 0) {
                console.log('false');
                return false;
            }
            const top = stack.pop();
            console.log(top, 'stack.pop()');
            if (top === '(' && char !== ')') {
                console.log('false');
                return false;
            }
            if (top === '{' && char !== '}') {
                console.log('false');
                return false;
            }
            if (top === '[' && char !== ']') {
                console.log('false');
                return false;
            }
        }
    }
    console.log(true);
    return stack.length === 0;
};

测试一下，我们写法ok

优化方案二

优化，我们可以使用in操作符对于表达式优化写法

// 解法二 优化写法
function isValid(str) {
    const stack = [];
    const bracketMap = {
        '(': ')',
        '{': '}',
        '[': ']'
    };
    for (let i = 0; i < str.length; i++) {
        const char = str[i];
        if (char in bracketMap) {
          console.log(char,'char--')
            // 如果是左括号，压入栈中
            stack.push(char);
        } else {
            // 如果是右括号
            if (stack.length === 0 || bracketMap[stack.pop()] !== char) {
                console.log('false');
                return false;
            }
        }
    }
    console.log(true);
    return stack.length === 0;
}
isValid(s);

优化为右括号压栈

上面我们的写法都是压入左括号然后进行入栈，我们可以直接入栈右括号，判断的时候就非常方便

也就相当于我们直接拿} 对比 }

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function (str) {
    const stack = [];
    const bracketMap = {
        '(': ')',
        '{': '}',
        '[': ']'
    };
    for (let i = 0; i < str.length; i++) {
        const char = str[i];
        if (char in bracketMap) {
            stack.push(bracketMap[char]); // 直接压入对应的右括号
        } else if (stack.length === 0 || stack.pop() !== char) {
            return false;
        }
    }
    return stack.length === 0;
}

测试一下，ok

优化写法

最后优化一下我们的写法

 // 解法三 优化右符号压栈
    function isValid(str) {
        const stack = [];
        const mapData = {
            "{": "}",
            "(": ")",
            "[": "]",
        };
        for (const char of str) {
            if (char in mapData) {
                stack.push(mapData[char]);
            } else if (stack.length === 0 || stack.pop() !== char) {
                return false
            };
        }
        return stack.length === 0
    }

测试

 // 测试示例
    const testCases = [
        "()",
        "()[]{}",
        "(]",
        "([)]",
        "{[]}"
    ];

    testCases.forEach(s => {
        console.log(`"${s}": ${isValid(s)}`);
    });

测试OK