Leetcode基础刷题之PHP解析(20. Valid Parentheses)
2019-6-17 星期一 开始吧
回溯法的题目暂时告一段落吧
上一题链接Leetcode基础刷题之PHP解析(79. Word Search)
题目描述
这是一道easy类型的题目,字符串只包含三对开,关的字符串,根据输入的字符串,判断是否为有效的字符串,必须以相同类型的字符串关闭左括号,必须以正确的顺序开关括号。
题目分析
最常规的解决就是定义一个三对括号相对应的键值对数组,定义一个格外的数组用来存储没有匹配的括号字符串。只要不匹配,就把他丢进数组中,每次取数组中最后一个元素和当前遍历的字符串位置值相比较,如果相等,说明匹配,从数组中拿走。最后判断数组是否为空即可。
xxxxxxxxxx
/**
* @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;
}
换一种暴力点,好吧,确实很暴力,但是效率低下。
xxxxxxxxxx
/**
* @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
No Comments