LeetCode第20题
Given a string containing just the characters ‘(‘, ‘)‘, ‘{‘, ‘}‘, ‘[‘ and ‘]‘, determine if the input string is valid.
An input string is valid if:
Note that an empty string is also considered valid.
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
思路：
本来我的想法是不管()，[]，{}，都是在一起的，我一对一对的删掉，最后删空了，就符合要求
代码
class Solution { public boolean isValid(String s) { if(s.length()>Integer.MAX_VALUE){ return true; } for(int i = 0;i<3;i++){ for(int j = 0;j<s.length();j++){ s = s.replace("()",""); System.out.println(s); s = s.replace("[]",""); System.out.println(s); s = s.replace("{}",""); System.out.println(s); } } if("".equals(s)){ return true; }else{ return false; } } }
结果
搞这么多符号，这不故意整我吗
百度了下，都说用栈，代码如下
class Solution { public boolean isValid(String s) { Stack<String> stack = new Stack<String>(); for (int i = 0; i < s.length(); i++) { char candidate = s.charAt(i); if (candidate == ‘{‘ || candidate == ‘[‘ || candidate == ‘(‘) { stack.push(candidate + ""); } else { if (stack.isEmpty()) { return false; } if ((candidate == ‘}‘ && stack.peek().equals("{")) || (candidate == ‘]‘ && stack.peek().equals("[")) || (candidate == ‘)‘ && stack.peek().equals("("))) { stack.pop(); } else { return false; } } } if (stack.isEmpty()) { return true; } else { return false; } } }
就是利用后进先出的原理，其实跟我的思路差不多，但是性能要好很多，哈哈
原文：https://www.cnblogs.com/anni-qianqian/p/9061561.html