Leetcode基础刷题之PHP解析(20. Valid Parentheses)

2019-6-17 星期一 开始吧

回溯法的题目暂时告一段落吧

上一题链接Leetcode基础刷题之PHP解析(79. Word Search)

题目描述

这是一道easy类型的题目，字符串只包含三对开,关的字符串,根据输入的字符串，判断是否为有效的字符串，必须以相同类型的字符串关闭左括号，必须以正确的顺序开关括号。

题目分析

最常规的解决就是定义一个三对括号相对应的键值对数组,定义一个格外的数组用来存储没有匹配的括号字符串。只要不匹配，就把他丢进数组中，每次取数组中最后一个元素和当前遍历的字符串位置值相比较，如果相等，说明匹配，从数组中拿走。最后判断数组是否为空即可。

/**
     * @param String $s
     * @return Boolean
     */
    function isValid($s) {
        $list=['{'=>'}','['=>']','('=>')'];
        $res=[];
        for($i=0;$i<strlen($s);$i++){
            $tmp=end($res);
            if($list["$tmp"] == $s[$i]){
                unset($res[key($res)]);
            }else{
                $res[]=$s[$i];
            }
        }
        return count($res)==0;
   }

换一种暴力点，好吧，确实很暴力，但是效率低下。

   /**
     * @param String $s
     * @return Boolean
     */
    function isValid($s) {
       do{
            $s=str_replace(['()','[]','{}'],'',$s,$count);
        }while($count);
        return empty($s);
    }

Github整理地址:https://github.com/wuqinqiang/leetcode-php