问题描述
https://leetcode.com/problems/valid-parentheses/
解决思路(2019-12-07)
- use stack to store all left parentheses
- if encounter right parenthesis, pop the parenthese in stack
- if poped parenthsis corresponding the left, return true, or return false
- if the stack is not empty, it still returns false
代码
class Solution {
public boolean isValid(String s) {
//1. use stack to store all left parentheses
//2. if encounter right parenthesis, pop the parenthese in stack
//3. if poped parenthsis corresponding the left, return true, or return false
//4. if the stack is not empty, it still returns false
//corner case
if(s == null) return false;
if(s.length() == 0) return true;
Stack stack = new Stack();
boolean flag = true;
HashMap<Character, Character> map = new HashMap<>();
map.put('}', '{');
map.put(']', '[');
map.put(')', '(');
for(int i = 0; i < s.length(); i++){
//if left parenthese, push in the stack
if(s.charAt(i) == '(' || s.charAt(i) == '[' || s.charAt(i) == '{'){
stack.push(s.charAt(i));
}else{
//if right parenthese cannot pair to its correponding left parenthese,
//or there is not left parenthese in the stack to pair with the right
if(stack.isEmpty() || stack.peek() != map.get(s.charAt(i))){
flag = false;
break;
}else{//pop the left out of the stack
stack.pop();
}
}
}
//if stack still has left parenthese not be paired
if(stack.size() != 0){
flag = false;
}
return flag;
}
}
复杂度分析
时间复杂度：O(N) 空间复杂度：O(N)
解决思路(2019-06-28)
首先利用HashMap将括号成对存入，然后通过栈，如果遇到左半边括号，就压栈，如果遇到右半边括号，先判断栈元素是否为空（如果为空，则没有左半边括号，return false），并且判断，pop出来的元素，是否为对应的另一半左括号，不是则return false，否则return true。
最后，循环结束，如果栈内元素全部弹出，则完全匹配；若仍有剩余，则匹配不完全，return false.
代码
package leetcode;
import java.util.HashMap;
import java.util.Stack;
public class ValidParentheses {
public boolean isValid(String s) {
Stack<Character> st = new Stack<>();
HashMap<Character, Character> map = new HashMap<>(){
{
put(')','(');
put(']','[');
put('}','{');
}
};
char chrs[] = s.toCharArray();
for (Character c : chrs) {
switch (c){
case '{':
case '(':
case '[':
st.push();
break;
case '}':
case ']':
case ')':
if (st.empty() || st.pop() != map.get(c)) return false;
}
}
return st.empty();
}
}
小感想
- 遇到字符串问题，可以尝试将其转化为字符数组解决。
- 遇到配对问题，可以尝试使用HashMap解决。
