Simple Balanced Parentheses(Phone Interview)


  • 0
    J

    Write a program to check if a given input string has valid parenthesis or not.

    For Example:
    Input : [()]{}()()}
    Output : false

    Input : {[[([])]]}
    Output : True


  • 0
    L

    @jayp The possible solution is using a HashMap to store the paired parentheses. Key is left sign and value is right. Then scan the input string and using a Stack to tracking the inputed parenthesis. Push left sign into the stack and pop right sign out of the stack. Compare the last index of Pop and the first of Push, if last.index.push > first.index.pop, return false. After completed scan, check Stack is empty, return true; else return false.


  • 0

    @jayp seems like both examples are valid parenthesis. Is your question different from Q20 "Valid Parenthesis" of LeetCode? If yes, can you explain your question in more detail?


  • 0
    J

    @ramanpreetSinghKhinda Thanks for pointing out the typo. I corrected the first input. It was supposed to have one less open braces. You are right Q20. "Valid Parenthesis" question is exactly what they asked but different wordings.


  • 0
    L

    @laqxs See my sample Java Solution below:

        public static boolean isBalanced(String p) {
            if( p == null || p.length() == 0) return true;
    
            Stack<Character> stack = new Stack<Character>();
            Character right = null;
            for(char c: p.toCharArray()) {
                switch (c) {
                    case '(':
                        stack.push(c);
                        break;
                    case ')':
                        if(stack.isEmpty()) return false;
                        right = stack.pop();
                        if( right == null || !right.equals( '(')) {
                            return false;
                        }
                        break;
    
                    case '[':
                        stack.push(c);
                        break;
                    case ']':
                        if(stack.isEmpty()) return false;
                        right = stack.pop();
                        if( right == null || !right.equals( '[')) {
                            return false;
                        }
                        break;
    
                    case '{':
                        stack.push(c);
                        break;
                    case '}':
                        if(stack.isEmpty()) return false;
                        right = stack.pop();
                        if( right == null || !right.equals( '{')) {
                            return false;
                        }
                        break;
                    default:
    
                }
            }
            return true;
        }
    

  • 0
    
    
    Use this Simple approach for all the braces..
    
    function checkforBraces(input)
    {  
       var i = input;
        var oCount = 0;
           var cCount = 0;
        for(var index = 0; index <=  i.length - 1; index++){   
            if(input[index] == '{'){
                oCount ++;
            } else if(input[index] == '}') {
                cCount++;
                oCount --;
            }  
            
            if (oCount < 0) { return false;}
        }
        
        if(oCount > 0) { return false; }
        
        return true;
    }

  • 0
    M

    Here is a python 3 implementation:

    def balanced_parens(s):
        if len(s) == 0:
            return True
        stack = collections.deque()
        matches = {')': '(',
                   ']': '[',
                   '}': '{'}
        for k in s:
            if k in ']})' and len(stack) == 0:
                return False
            elif k in '[{(':
                stack.append(k)
            else:
                v = stack.pop()
                if matches[k] != v:
                    return False
        return True
    

  • 0
    public bool IsValid(string s)
    {
        Stack<char> stack = new Stack<char>();
                for(int i = 0;i<s.Length;i++)
                {
                    if(s[i] == '(')
                    {
                        stack.Push(')');
                    }
                    else if(s[i] == '{')
                    {
                        stack.Push('}');
                    }
                    else if(s[i] == '[')
                    {
                        stack.Push(']');
                    }
                    else if( stack.Count > 0 && s[i] == stack.Peek())
                    {
                        stack.Pop();
                    }
                    else
                    {
                        return false;
                    }                           
                }            
                return stack.Count == 0;
        
    }
    
    
    

  • 0
    A
    This post is deleted!

Log in to reply
 

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