Java solution with stack, very easy to read, straightforward


  • 9
    J
    public class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<Character>();
        if(s.equals("")) return true;
        for(char ch : s.toCharArray()){
            if(ch=='('|| ch=='[' || ch=='{'){
                stack.push(ch);
            } else if(ch==')'){
                if(stack.empty() || stack.pop()!='(')
                    return false;
            } else if(ch==']'){
                if(stack.empty() || stack.pop()!='[')
                    return false;
            } else if(ch=='}'){
                if(stack.empty() || stack.pop()!='{')
                    return false;
            }
        }
        return stack.empty();
    }
    

    }


  • 2
    D

    I think it's a little more elegant and concise to use a HashMap, take a look:

     public class Solution {
        public boolean isValid(String s) {
            HashMap<Character, Character> map = new HashMap<Character, Character>();
            map.put('(', ')');
            map.put('{', '}');
            map.put('[', ']');
            Stack<Character> stk = new Stack<Character>();
            for (int i = 0; i < s.length(); i++){
                if (map.containsKey(s.charAt(i))){
                    stk.push(s.charAt(i));
                }
                else{
                    if (stk.empty()){
                        return false;
                    }
                    if (s.charAt(i) == map.get(stk.peek())){
                        stk.pop();
                    }
                    else{
                        return false;
                    }
                }
            }
            return (stk.empty());
        }
    }

  • 0
    M

    Nice one Joshua, just a couple of tips. Instead of Stack use Deque. It is generally faster (although the asymptotic complexity is the same) and can be easily transformed into a queue when needed.
    Secondly, you can simplify your return statement with "return stack.empty();". I believe it is way more readable


  • 0
    J

    Nice solution. Just a small improvement, faster by checking if s.length() is even.


  • 0
    J

    Sorry I just see this, and it's very good suggestions, especially the return part. What I've written is totally unnecessary. Edited.


  • 0
    C

    Very nice solution! Thanks!


Log in to reply
 

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