leetcode 20 : 有效的括号
给定一个只包括 '('
,')'
,'{'
,'}'
,'['
,']'
的字符串 s
,判断字符串是否有效。
有效字符串需满足:
-
左括号必须用相同类型的右括号闭合。
-
左括号必须以正确的顺序闭合。
示例 1:
输入:s = "()" 输出:true
示例 2:
输入:s = "()[]{}" 输出:true
示例 3:
输入:s = "(]" 输出:false
示例 4:
输入:s = "([)]" 输出:false
示例 5:
输入:s = "{[]}" 输出:true
提示:
-
1 <= s.length <= 104
-
s
仅由括号'()[]{}'
组成
Related Topics
栈
字符串
思路1:栈
public boolean isValid(String s) { int length = s.length(); char[] stack = new char[length]; int last = -1; for(int i = 0 ; i < length;i++){ char c = s.charAt(i); if(c == '(' || c == '{' || c=='['){ stack[++last] = c; }else{ // ) ] } 进行匹配出栈 if(last==-1 ){ //需要匹配时 没有元素 例:]][[ return false; } //匹配成功 出栈 if((c == ')' && stack[last] == '(') || (c == '}' && stack[last] == '{') || (c ==']' && stack[last] == '[')){ last--; }else{//不成功 return false; } } } return last==-1? true :false; }
思路2:
对思路1改进:
public boolean isValid(String s) { int length = s.length(); char[] stack = new char[length]; int last = -1; for(int i = 0 ; i < length;i++){ char c = s.charAt(i); // 左括号 if(c == '(' || c == '{' || c=='['){ stack[++last] = c; //匹配成功 出栈 }else if(last != - 1 && ((c == ')' && stack[last] == '(') || (c == '}' && stack[last] == '{') || (c ==']' && stack[last] == '[') )){ last--; }else{//不成功 return false; } } return last==-1; }