Valid Parentheses using Java


  • 0
    G

    Approach #1 Stack Algorithm

    Algorithm

    The naive approach ...

    Java

    class Solution {
        public boolean isValid(String s) {
            Stack<Character> stack = new Stack<Character>();
            Map<Character, Character> map = new HashMap<Character, Character>();
            map.put(')', '(');
            map.put(']', '[');
            map.put('}', '{');
            
            for (int i = 0; i < s.length(); i++)
            {
                Character ch = s.charAt(i);
                if (ch == '(' || ch == '[' || ch == '{')
                    stack.push(ch);
                else if (ch == ')'|| ch == ']' || ch == '}')
                {
                    //nothing to match with
                    if(stack.isEmpty())
                    {  
                        return false;
                    }
                    else
                    { 
                        Character popCh = stack.pop();
                        Character newCh = map.get(ch);
                        if(newCh != popCh) {
                            return false;
                        }
                    }
                }
            }
            if (stack.isEmpty())
            {
                return true;
            }
            else
            {
                return false;
            }
        }
    }
    

    Complexity Analysis

    • Time complexity : It runs in O(N) time with O(N) worst case space complexity for the stack

Log in to reply
 

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