[LeetCode]Valid Parentheses

Valid Parentheses

檢查字串當中，是否包含有效的括號 ()、[]、{}。其有效定義為

1. 括號的頭尾必須是相同類型的括號
2. 括號的頭尾的順序必須正確

Example 1

Input: s = "()"
Output: true

Example 2

Input: s = "()[]{}"
Output: true

Example 3

Input: s = "(]"
Output: false

解法

可用正規式進行比對，並把匹配的括號移除，反覆執行直到再也找不到對應的括號。但執行效率大多落在60-70ms，明顯不是最佳解。

class Solution
{

    /**
     * @param String $s
     * @return Boolean
     */
    function isValid($s)
    {
        if (
            preg_match('/\(\)/', $s, $matches) ||
            preg_match('/\[\]/', $s, $matches) ||
            preg_match('/\{\}/', $s, $matches)
        ) {
            if (preg_match('/\(\)/', $s, $matches))
                $s = str_replace('()', '', $s);
            if (preg_match('/\[\]/', $s, $matches))
                $s = str_replace('[]', '', $s);
            if (preg_match('/\{\}/', $s, $matches))
                $s = str_replace('{}', '', $s);

            if ($s == '')
                return true;
            else
                return $this->isValid($s);
        } else {
            return false;
        }
    }
}

另一種是使用後進先出的方式，按照順序儲存左括號，當右括號比對陣列最後一個字元為同類型的左括號，用 array_pop() 將最後面元素取消掉一個。也因為括號都是成對的，因此只要字串長度非偶數，則直接回傳 false。

以 (([]){}) 為例：

class Solution
{

    /**
     * @param String $s
     * @return Boolean
     */
    function isValid($s)
    {
        $strs = str_split($s);

        if (count($strs) % 2 == 1)
            return false;

        // 定義左括號、右括號陣列
        $arr_dic = array(
            '(' => ')',
            '{' => '}',
            '[' => ']'
        );

        $arr_stack = array();
        foreach ($strs as $c) {
            if ($arr_dic[$c]) {
                array_push($arr_stack, $arr_dic[$c]);
            } else {
                // array_pop 回傳陣列最後一個值，並移除最後一個元素
                $temp_c = array_pop($arr_stack);
                if ($temp_c != $c)
                    return false;
            }
        }

        if (count($arr_stack) == 0)
            return true;
        else
            return false;
    }
}

參考：array_pop