My O(n) Java solution using a stack


  • 0
    C

    Standard solution using stack. The only simplification is to use ASCII to determine matches.
    Please feel free to point any mistakes or suggest any improvements! Thanks a lot!

    public class Solution {
        public boolean isValid(String s) {
            if (s.length() == 0){
                return true;
            }
            if (s.length() % 2 == 1){
                return false;
            }
            Stack<Character> st = new Stack<Character>();
            for (int i = 0; i < s.length(); i++){
                if (s.charAt(i) == '(' || s.charAt(i) == '[' || s.charAt(i) == '{'){
                    st.push(s.charAt(i));
                }else{
                    if (st.isEmpty()){
                        return false;
                    }
                    if (s.charAt(i) - st.peek() > 2){
                        return false;
                    }else{
                        st.pop();
                    }
                }
                
            }
            return st.isEmpty();
        }
    }

  • 0
    L

    I think it should be " s.charAt(i) - st.peek() > 2". Although I think it's a mistake, your function pass the test. It confuses me a lot. What do you think?

    What's more, if the length of strs is odd, the result must be false.


  • 0
    C

    Thank you very much for your correction! I have edited my code. Now I guess everything should be right. I guess the standard test cases didn't include cases like "(}".


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.