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

有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

示例 1：
输入：s = "()"
输出：true

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

示例 3：
输入：s = "(]"
输出：false

示例 4：
输入：s = "([])"
输出：true

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

思路:
不断消除相邻的有效括号,每次消除后必定产生新的有效括号,否则返回false,直到字符串为空,返回true

代码:
function isValid($s) {
    $map = [
        '(' => ')',
        '[' => ']',
        '{' => '}',
    ];

    $i = 0;
    while (1) {
        if (!isset($s[$i + 1])) {
            break;
        }

        $now = $map[$s[$i]] ?? '';

        if ($now == $s[$i + 1]) {
            $s = substr_replace($s, '', $i, 2);
            $i = 0;
        } else {
            $i++;
        }
    }

    if ($s) {
        return false;
    }

    return true;
}

思路:
将遍历过的字符存入数组中,如果遇到右半边的括号,从数组中弹出一个字符,如果弹出的字符和右边的括号不匹配,返回false,
如果遍历一遍的字符后,数组内还有剩余的字符,返回false

代码:
function isValid($s) {
    $map = [
        ')' => '(',
        ']' => '[',
        '}' => '{',
    ];

    $len = strlen($s);

    $arr = [];
    for ($i = 0; $i < $len; $i++) {
        if (isset($map[$s[$i]])) {
            $f = array_shift($arr);

            if (null === $f) {
                return false;
            }

            if ($f !== $map[$s[$i]]) {
                return false;
            }
        } else {
            array_unshift($arr, $s[$i]);
        }
    }

    if ($arr) {
        return false;
    }

    return true;
}

思路:
思路与解法2相同,将array_shift改为array_pop,提高性能
array_pop() 的性能更优,时间复杂度:O(1),只需要移除数组最后一个元素,不需要重新索引数组
array_shift() 性能较差,时间复杂度:O(n),移除第一个元素后,PHP 会自动将数组中剩余元素的键值向前移动（重新索引）,这是一个线性操作,耗费时间随数组长度增加。

代码:
function isValid($s) {
    $map = [
        ')' => '(',
        ']' => '[',
        '}' => '{',
    ];

    $len = strlen($s);

    $arr = [];
    for ($i = 0; $i < $len; $i++) {
        if (isset($map[$s[$i]])) {
            $f = array_pop($arr);

            if (null === $f) {
                return false;
            }

            if ($f !== $map[$s[$i]]) {
                return false;
            }
        } else {
            $arr[] = $s[$i];
        }
    }

    if ($arr) {
        return false;
    }

    return true;
}