Given a string containing just the characters '('
, ')'
, '{'
, '}'
, '['
and ']'
,
determine if the input string is valid.
The brackets must close in the correct order, "()"
and "()[]{}"
are
all valid but "(]"
and "([)]"
are not.
字符串中只有各种括号,判断这个字符串括号规则是否匹配。
1 首先要看清楚规则,如何;这道题目比较简单,只能够就近匹配;那么只要碰到( [ { 入栈,碰到 ) ] }入栈检查是否匹配上一个就可以;如果在检查中栈empty了,说明无可以匹配项目,输出false; 如果匹配完成,最后栈没有empty,说明有多余的,输出false。
2 上面的想法基本是考虑到栈后就有了,所以写代码的时候基本一次通过。
3 如果考虑更加复杂一点,可以间隔匹配,那么可以考虑加一个栈。每次检查的时候,都需要把不对应匹配的括号先入到另外一个栈中去;找到匹配的
再放回即可。
代码
public class Solution { public boolean isValid(String s) { if(s==null|| s.length()==1){ return false; } if(s.length()==0){ return true; } Stack<Character> record = new Stack<Character>(); for(int i =0;i<s.length();i++){ char cur = s.charAt(i); if(cur=='('||cur=='{'||cur=='['){ record.push(cur); continue; } if(cur==')'){ if(record.isEmpty()||record.pop()!='('){ return false; } } if(cur=='}'){ if(record.isEmpty()||record.pop()!='{'){ return false; } } if(cur==']'){ if(record.isEmpty()||record.pop()!='['){ return false; } } } if(!record.isEmpty()){ return false; } return true; } }
细节
测试