import java.util.*;
/**
给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
来源:力扣(LeetCode)
-
链接:https://leetcode-cn.com/problems/valid-parentheses
/
public class EffectiveBrackets {
/*利用栈来实现,如果遇见右括号,判断栈顶元素是不是对应的左括号,是则继续匹配,不是则返回false
时间复杂度:O(n)O(n),因为我们一次只遍历给定的字符串中的一个字符并在栈上进行 O(1)O(1) 的推入和弹出操作。
空间复杂度:O(n)O(n),当我们将所有的开括号都推到栈上时以及在最糟糕的情况下,我们最终要把所有括号推到栈上。例如 ((((((((((
@param s
-
@return
*/
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
Map<Character,Character> correctBrackets = new HashMap<>();
correctBrackets.put(')','(');
correctBrackets.put(']','[');
correctBrackets.put('}','{');
for(int i=0;i<s.length();i++) {
char c = s.charAt(i);
if(correctBrackets.containsKey(c)){
if(stack.isEmpty()||stack.pop()!=correctBrackets.get(c)) return false;
}else stack.push(c);}
return stack.isEmpty();
}
public static void main(String[] args){
EffectiveBrackets effectiveBrackets = new EffectiveBrackets();
System.out.println(effectiveBrackets.isValid("()[]{}"));
}
}