首页 > 代码库 > LeetCode--Valid Parentheses

LeetCode--Valid Parentheses

2024-08-09 04:50:42   215人阅读

这个题目我采用了两种方案，第一种方案代码行数相对较少，但效率稍低，第二种方案参照网上的进行改进代码行数相对多些，但效率稍高。

题目：

Given a string containing just the characters ‘(‘, ‘)‘, ‘{‘, ‘}‘, ‘[‘ and ‘]‘, determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

第一种解决方案：

import java.util.HashMap;
import java.util.Map;
public class Solution {
    public boolean isValid(String s) {
        Map<Character,Character> map=new HashMap<Character,Character>();
        map.put(']','[');
        map.put('}','{');
        map.put(')','(');
        Stack<Character> st=new Stack<Character>();
        for(int i=0;i<s.length();i++){
           Character c=s.charAt(i);
            if(c==']'||c=='}'||c==')'){
                if(st.size()==0)return false;
                Character top=st.peek();
                if(top.equals(map.get(c))){
                    st.pop();
                }else{
                    return false;
                }
                
            }else{
                st.push(c);
            }
        }
        return st.size()==0?true:false;
    }
}


第二种解决方案：

import java.util.HashMap;
import java.util.Map;


public class Solution {
    public boolean isValid(String s) {
        Stack<Character> st = new Stack<Character>();

        for (int i = 0; i < s.length(); i++) {
            Character c = s.charAt(i);

            if ((c == ']') || (c == '}') || (c == ')')) {
                if (st.empty()) {
                    return false;
                }

                Character pre = st.peek();

                switch (c) {
                case ')':

                    if (pre == '(') {
                        st.pop();
                    } else {
                        return false;
                    }

                    break;

                case '}':

                    if (pre == '{') {
                        st.pop();
                    } else {
                        return false;
                    }

                    break;

                case ']':

                    if (pre == '[') {
                        st.pop();
                    } else {
                        return false;
                    }

                    break;
                }
            } else {
                st.push(c);
            }
        }

        return st.empty() ? true : false;
    }
}


LeetCode--Valid Parentheses


联系
我们