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

2019-6-17 期一 

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


Leetcode基础刷题之PHP解析(79. Word Search)

d5547f0a0cc20bd26591abf8f99b65b1.png



这是一道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

上一篇: Beego 框架入门篇:通过 Beego 提供的脚手架工具 Bee 快速创建 Web 项目

下一篇: Leetcode PHP题解--D89 653. Two Sum IV - Input is a BST