leetcode 20. Valid Parentheses
Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.An input string is valid if:
Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
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 == null || s.length() == 0) return true;
if(s.length() == 1) return false;
int len = s.length();
Stack <Character> st = new Stack<>();
for(int i = 0; i< len; i++){
if(st.empty() && (s.charAt(i) == ')' || s.charAt(i) == ']' || s.charAt(i) == '}')) return false;
if(s.charAt(i) == '(') st.push(')');
if(s.charAt(i) == '[') st.push(']');
if(s.charAt(i) == '{') st.push('}');
if(s.charAt(i) == ')' && st.peek() == ')') st.pop();
else if(s.charAt(i) == ')') st.push(')');
if(s.charAt(i) == ']' && st.peek() == ']') st.pop();
else if(s.charAt(i) == ']') st.push(']');
if(s.charAt(i) == '}' && st.peek() == '}') st.pop();
else if(s.charAt(i) == '}') st.push('}');
}
if(st.empty()){
return true;
}
return false;
}
}
class Solution {
public boolean isValid(String s) {
// if(s == null || s.length() == 0) return true;
// if(s.length() == 1) return false;
int len = s.length();
Stack <Character> st = new Stack<>();
for(int i = 0; i< len; i++){
if(s.charAt(i) == '(') st.push(')');
else if(s.charAt(i) == '[') st.push(']');
else if(s.charAt(i) == '{') st.push('}');
else if (st.empty() || st.pop() != s.charAt(i)){
return false;
}
}
return st.empty();
}
}
页:
[1]