有效括号-栈 leetcode题库第二十题

来自力扣题库第20题

链接：https://leetcode-cn.com/problems/valid-parentheses

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 注意空字符串可被认为是有效字符串。

示例 1:

输入: "()" 输出: true

这个题可以用数据结构里面的栈进行实现（这是未优化的，优化后使用一个栈就可以，详情看最下方）

function a($str): bool {
    $leftStr  = ['[', '{', '('];//存储符号为左的
    $rightStr = [']', '}', ')'];//存储符号为右的 这里需要注意成对的符号，下标要一致
    /**
     * 这里使用数组函数array_push和array_pop进行模拟出入栈操作会比 new SplStack()方式内存占用更低一些
     */
    $leftStr  = array_flip($leftStr);
    $rightStr = array_flip($rightStr);
    $left     = new SplStack();//初始化存储符号为左的栈
    $right    = new SplStack();//初始化存储符号为右的栈
    $len      = strlen($str);
    //如果长度不是偶数直接返回false
    if ($len % 2) {
        return false;
    }
    for ($i = 0; $i < strlen($str); $i++) {
        if (isset($leftStr[$str[$i]])) {
            $left->push($str[$i]);
        } elseif (isset($rightStr[$str[$i]])) {
            $right->push($str[$i]);
        }
        //判断左符号栈和右符号栈都没有数据
        if (!$left->isEmpty() && !$right->isEmpty()) {
            //左符号栈和右符号栈都弹出一个符号进行比较，如果不一样就再放回去，进行下一次判断
            $leftLs  = $left->pop();
            $rightLs = $right->pop();
            if ($leftStr[$leftLs] != $rightStr[$rightLs]) {
                $left->push($leftLs);
                $right->push($rightLs);
            } elseif (isset($leftStr[$str[$i]])) {//判断出现类似 “}{”左右符号相反，程序判断为true的问题
                return false;
            }
        }
    }
    //如果左符号栈或右符号栈还有数据，就说明为false
    if (!$left->isEmpty() || !$right->isEmpty()) {
        return false;
    }
    return true;
}

还有一个更简洁的办法，不过这个运行效率不如上述办法

function b($str): bool {
    $count = ceil(strlen($str) / 2);
    for ($i = 0; $i < $count; $i++) {
        $str = str_replace("{}", "", $str);
        $str = str_replace("[]", "", $str);
        $str = str_replace("()", "", $str);
    }
    if ($str) {
        return false;
    }
    return true;
}

隔一天又更新，最近我在看极客时间的一个专栏，《数据结构预算法之美》，里面有一节就提到了栈，受到启发，我又重新优化了一下代码，如下

function c($str): bool {
    $rightStr = ['}' => '{', ']' => '[', ')' => '('];
    $leftStr  = array_flip($rightStr);
    /**
     * 这里使用数组函数array_push和array_pop进行模拟出入栈操作会比 new SplStack()方式内存占用更低一些
     */
    $left = new SplStack();//初始化存储符号为左的栈
    $len  = strlen($str);
    //如果长度不是偶数直接返回false
    if ($len % 2) {
        return false;
    }
    for ($i = 0; $i < strlen($str); $i++) {
        $ls = $str[$i];
        if (isset($leftStr[$ls])) {
            $left->push($ls);
        } elseif (isset($rightStr[$ls])) {
            if (!$left->isEmpty()) {
                $l = $left->pop();
                if ($l != $rightStr[$ls]) {
                    return false;
                }
            } else {
                return false;
            }
        }
    }
    //如果左符号栈或右符号栈还有数据，就说明为false
    if (!$left->isEmpty()) {
        return false;
    }
    return true;
}