Given a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[’ and ‘]’, determine if the input string is valid.
An input string is valid if:
Example 1:
Input: "()"
Output: true
Example 2:
Input: "()[]{}"
Output: true
Example 3:
Input: "(]"
Output: false
Example 4:
Input: "([)]"
Output: false
Example 5:
Input: "{[]}"
Output: true
//8ms
class Solution {
/**
* @param String $s
* @return Boolean
*/
function isValid($s) {
$corr = [
'(' => ')',
'[' => ']',
'{' => '}'
];
$arr = [];
$arrLen = 0;
$len = strlen($s);
for ($i = 0; $i < $len; $i++) {
$value = $s[$i];
switch ($value) {
case '(':
case '[':
case '{':
array_push($arr, $corr[$value]);
$arrLen += 1;
break;
default:
if ($arrLen == 0 || $arr[$arrLen-1] != $value) {
return false;
}
array_pop($arr);
$arrLen -= 1;
}
}
return $arrLen == 0;
}
}
//8ms
function isValid($s) {
if (!strlen($s)) return true;
$stack = [];
$couple = array("}"=>"{", ")" => "(", "]"=>"[");
foreach (str_split($s) as $v) {
if (!array_key_exists($v,$couple))
array_push($stack, $v);
elseif (!count($stack) || !($couple[$v] == array_pop($stack)))
return false;
}
return !count($stack);
}
public function isValid($s)
{
$eg = ["{" => "}", "[" => "]", "(" => ")"];
$arr = [];
for ($i = 0; $i < strlen($s); $i++) {
$tmp = end($arr);
if ($eg["$tmp"] == $s[$i]) {
unset($arr[key($arr)]);
} else {
$arr[] = $s[$i];
}
}
return count($arr) == 0;
}
//0ms
func isValid(s string) bool {
var q []rune
var l int = 0
for _,v := range s {
switch v {
case '(':
q = append(q, ')')
l += 1
case '[':
q = append(q, ']')
l += 1
case '{':
q = append(q, '}')
l += 1
default:
if l == 0 || q[l-1] != v{
return false
}
q = q[0:l-1]
l -= 1
}
}
return l == 0
}
func isValid(s string) bool {
stack := make([]rune, len(s))
top := 0
for _, c := range s {
switch (c) {
case '(' :
stack[top] = ')'
top+=1
break
case '{' :
stack[top] = '}'
top+=1
break
case '[' :
stack[top] = ']'
top+=1
break
default:
if top == 0 || stack[top-1] != c {
return false
}
top -=1
break
}
}
return top == 0
}
func isValid(s string) bool {
parentheses := map[rune]rune{')': '(', ']': '[', '}': '{'}
var stack []rune
for _, char := range s {
if char == '(' || char == '[' || char == '{' {
stack = append(stack, char)
} else if len(stack) > 0 && parentheses[char] == stack[len(stack) - 1] {
stack = stack[:len(stack) - 1]
} else {
return false
}
}
return len(stack) == 0
}
方法一一般是自己实现的方法，其他方式是在discuss中查找的更为优秀的方法，用作学习和借鉴。