D135 20. Valid Parentheses

题目链接

20. Valid Parentheses

题目剖析

这道题也比拟经典，就是括号匹配题。

给出一个蕴含小、中、大括号的字符串，判断左右括号是否匹配。

要留神呈现程序，不能串。也要留神有可能会呈现空字符串。

解题思路

这道题的经典做法是用栈来实现。

遇到左括号时，间接入栈。遇到右括号时，判断以后括号类型和栈顶端，即出栈时的括号类型是否雷同。如果雷同则持续判断。如果不同则返回false。

遍历完所有字符时，如果栈内还有括号残余，即有括号没有被匹配，也视为false。

最终代码

<?php

class Solution {

    /**
     * @param String $s
     * @return Boolean
     */
    function isValid($s) {
        if(!strlen($s)){
            return true;
        }
        $parentheses_array = str_split($s);
        $stack = [];
        foreach($parentheses_array as $parenthes){
            if($parenthes == '(' 
              || $parenthes == '['
              || $parenthes == '{'){
                $stack[] = $parenthes;
            }
            else{
                $prev = array_pop($stack);
                if(( $prev== '(' && $parenthes == ')')
                   || ($prev == '[' && $parenthes == ']')
                   || ($prev == '{' && $parenthes == '}')
                   ){
                    continue;
                }
                return false;
            }
        }
        var_dump(count($stack));
        if(count($stack)){
            return false;
        }
        else{
            return true;
        }
    }
}

若感觉本文章对你有用，欢送用爱发电赞助。