My easy to understand Java Solution with one stack


  • 83
    K
    public class Solution {
        public boolean isValid(String s) {
            Stack<Character> stack = new Stack<Character>();
            // Iterate through string until empty
            for(int i = 0; i<s.length(); i++) {
                // Push any open parentheses onto stack
                if(s.charAt(i) == '(' || s.charAt(i) == '[' || s.charAt(i) == '{')
                    stack.push(s.charAt(i));
                // Check stack for corresponding closing parentheses, false if not valid
                else if(s.charAt(i) == ')' && !stack.empty() && stack.peek() == '(')
                    stack.pop();
                else if(s.charAt(i) == ']' && !stack.empty() && stack.peek() == '[')
                    stack.pop();
                else if(s.charAt(i) == '}' && !stack.empty() && stack.peek() == '{')
                    stack.pop();
                else
                    return false;
            }
            // return true if no open parentheses left in stack
            return stack.empty();
        }
    }

  • 1
    E

    why you need !stack.empty() in each else if?


  • 2
    K

    you need !stack.empty() to handle invalid input and because you can't peek when the stack is empty.


  • 2
    W

    I guess what he mean is you can write stack.empty() only once in a single 'else if' statement instead of mention it 3 times.


  • 53

    I used switch and it's faster. The code is longer but it's easy to understand.

    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            switch (s.charAt(i)) {
                case '(':
                    stack.push('(');
                    break;
                case '{':
                    stack.push('{');
                    break;
                case '[':
                    stack.push('[');
                    break;
                case ')':
                    if (stack.size() == 0 || stack.pop() != '(')
                        return false;
                    break;
                case '}':
                    if (stack.size() == 0 || stack.pop() != '{')
                        return false;
                    break;
                case ']':
                    if (stack.size() == 0 || stack.pop() != '[')
                        return false;
                    break;
            }
        }
        return stack.isEmpty();
    }

  • 0
    J
    This post is deleted!

  • 0
    This post is deleted!

  • -2
    E
    This post is deleted!

  • 0
    E

    Yes, the empty check can be extracted and put as the first else if condition.


  • 0
    E

    Could the person downvoted this one provide with a reason?


  • 0
    H

    nice code and pretty clear to understand :)


  • 11

    Concise Version

    public class Solution {
        public boolean isValid(String s) {
            if(s==null||s.length()%2==1)
                return false;
            Stack<Character> stack = new Stack<>();
            for(int i=0;i<s.length();i++){
                char c = s.charAt(i);
                if(c=='['||c=='{'||c=='(')
                    stack.push(c);
                else{
                    if(stack.isEmpty())
                        return false;
                    else if(c==']' && stack.pop()!='[')
                        return false;
                    else if(c==')' && stack.pop()!='(')
                        return false;
                    else if(c=='}' && stack.pop()!='{')
                        return false;
                }
            }
            return stack.isEmpty();
        }
    }

  • 0
    E

    Nice solution. Here is a cleaner and more concise version of code

    public class Solution {
        public boolean isValid(String s) {
            LinkedList<Character> stack = new LinkedList<>();
            Map<Character, Character> hm = new HashMap<>();
            hm.put(')', '(');
            hm.put(']', '[');
            hm.put('}', '{');
            for (int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);
                if (hm.containsKey(c)) {
                    if (stack.isEmpty() || !hm.get(c).equals(stack.pop())) {
                        return false;
                    }
                } else {
                    stack.push(c);
                }
            }
            return stack.isEmpty();
        }
    }
    

  • 0
    C

    Could anybody tell me why we cannot use .equals() instead of != ?


  • 0
    M

    i prefer this one


  • 0
    B

    Feel free to correct me if I'm wrong, but I believe the comparison here is through 'char' not 'Character'. Char is a primitive type, and does not have a .equals() method like Character does.


  • 0
    B

    Creative solution! I do think the original is easier to understand however, although I do like using the hashmap key values to map the correct bracket value.


  • -2
    C
    This post is deleted!

  • 1
    F
    public class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for(char c:s.toCharArray()){
            if(!stack.empty() && match(stack.peek(), c)) {
                stack.pop();
            } else {
                stack.push(c);
            }
        }
        return stack.empty();
    }
    
    private boolean match(char peek, char c){
        return peek == '(' && c == ')'
            || peek == '[' && c == ']'
            || peek == '{' && c == '}';
    }}
    

    Seems better.


  • 1
    O

    [],{},() has ascII code difference no more than 2 --> the trick makes coding consice

    public class Solution {
        public boolean isValid(String s) {
            Stack<Character> st = new Stack();
            char[] c = s.toCharArray();
            for (char i : c)
                if (i == '(' || i == '{' || i == '[') st.push(i);
                else
                if (st.empty() || i - st.peek() > 2) return false;
                else
                    st.pop();
            return st.empty();
        }
    }

Log in to reply
 

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