给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。
有效字符串需满足: 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 注意空字符串可被认为是有效字符串。
使用栈来进行辅助求解。 1、创建一个空栈; 2、使用循环对字符串进行遍历转3,遍历完毕退出循环转7; 3、如果当前字符为'('、'{'、'['则进栈,转2; 4、如果当前字符为')'、'}'、']',转5; 5、如果栈为空,则返回false,匹配不成功,结束程序;栈不空,转6; 6、弹出栈顶元素,如果栈顶元素不是与当前遍历到的字符相匹配的括号,则返回false,匹配不成功,结束程序;否则转2; 7、如果栈为空,则匹配成功,返回true,程序结束;否则返回false,匹配不成功,程序结束。
import java.util.Stack;
class Solution {
public boolean isValid(String s) {
Stack<Character> stack_match = new Stack<Character>();
for(int i=0;i<s.length();i++){
if(s.charAt(i)=='(' || s.charAt(i)=='[' || s.charAt(i)=='{'){
stack_match.push(s.charAt(i));
}else if(s.charAt(i)==')' || s.charAt(i)==']' || s.charAt(i)=='}'){
if(stack_match.isEmpty())
return false;
char current = stack_match.pop();
if(current == '(' && s.charAt(i)!=')')
return false;
if(current == '[' && s.charAt(i)!=']')
return false;
if(current == '{' && s.charAt(i)!='}')
return false;
}
}
if(stack_match.isEmpty())
return true;
return false;
}
}
案例1:“( )” 1、创建空栈; 2、对字符串进行遍历; 3、第一个元素是”(” 进栈;当前栈中元素有”(”; 4、第二个元素是”)”,栈非空,弹出栈顶元素;栈顶元素为”(”,与”)”可以匹配; 5、字符串遍历完毕,栈空,返回true
案例2:“{ }[ ]” 1、创建空栈; 2、对字符串进行遍历; 3、第一个元素是”{” 进栈;当前栈中元素有”{”; 4、第二个元素是”}”,栈非空,弹出栈顶元素;栈顶元素为”{”,与”}”可以匹配; 5、第三个元素是”[”,进栈;当前栈中元素有”[”; 6、第二个元素是”]”,栈非空,弹出栈顶元素;栈顶元素为”[”,与”]”可以匹配; 7、字符串遍历完毕,栈空,返回true
案例3:”( ) ) ]” 1、创建空栈; 2、对字符串进行遍历; 3、第一个元素是”(” 进栈;当前栈中元素有”(”; 4、第二个元素是”)”,栈非空,弹出栈顶元素;栈顶元素为”(”,与”)可以匹配; 5、第三个元素是”)”,栈空,返回false,匹配不成功,程序结束。
案例4:”( ( ( { [ } ] ) )” 1、创建空栈; 2、对字符串进行遍历; 3、第一个元素是”(” 进栈;当前栈中元素有”(”; 4、第二个元素是”(” 进栈;当前栈中元素有”( (”;; 5、第三个元素是”(” 进栈;当前栈中元素有”( ( (”; 6、第四个元素是”{” 进栈;当前栈中元素有”( ( ( {”; 7、第五个元素是”[” 进栈;当前栈中元素有”( ( ( { [”; 8、第六个元素是”}”,栈非空,弹出栈顶元素;栈顶元素为”[”,与”}”不可以匹配,返回false,程序结束。
扫下方二维码即可关注:
微信公众号:code随笔