My solution: One Stack, Case Statements, O(n)


  • 1
    A

    What I had tried to do earlier was try to combine all the closed-parentheses cases into the default case by checking if openStack.top() - s[i] == 1. I had assumed that the opened and closed versions of the characters were one ASCII number apart. But they aren't, it's even worse than that. The pairs {} and [] are two ASCII numbers apart, but the () characters are only one apart. Since I would have had to make a special case for the () characters, I decided to just make everything a case statement.

    Additionally, I think that by making the default case just continue, the isValid function will work for any string of any characters. That solution would be good for the more specific question of if the parentheses are valid in a mathematical expression.

     class Solution {
        public:
            bool isValid(string s)
            {
                std::stack<char> openStack;
                for(int i = 0; i < s.length(); i++)
                {
                    switch(s[i])
                    {
                        case '(':
                        case '{':
                        case '[':
                            openStack.push(s[i]);
                            break;
                        case ')':
                            if(!openStack.empty() && openStack.top() == '(' )
                                openStack.pop();
                            else
                                return false;
                            break;
                        case '}':
                            if(!openStack.empty() && openStack.top() == '{' )
                                openStack.pop();
                            else
                                return false;
                            break;
                        case ']':
                            if(!openStack.empty() && openStack.top() == '[' )
                                openStack.pop();
                            else
                                return false;
                            break;
                        
                        default:
                            return false;
                    }
                }
                
                if(openStack.empty())
                    return true;
                else
                    return false;
            }
        };

  • 3
    B

    Hi, my solution in Java is almost the same with yours, but with fewer lines.

    public boolean isValid(String s) {
    	if(s == null)
    		return true;
    	
        Stack<Character> stack = new Stack<>();
        for(char c: s.toCharArray())
        	switch(c){
        	case '(': case '{': case '[':
        	    stack.push(c); break;
        	case ')': 
        		if(stack.isEmpty() || stack.pop() != '(')
        			return false;
        		break;
        	case '}':
        		if(stack.isEmpty() || stack.pop() != '{')
        			return false;
        		break;
        	case ']':
        		if(stack.isEmpty() || stack.pop() != '[')
        			return false;
        	}
        return stack.isEmpty();
    }
    
    1. The if/else/stack.top in the case statement is not needed;
    2. You could just return statck.isEmpty();
    3. The beginning null check is not necessary but could be an optimistic;
    4. Yes, I let the default case continue... I just notice this when I read your question... but it passed.

  • 0
    H

    I put the isEmpty test in the first line in the for loop, it save some lines of code and two string left and right with the same order.

    public boolean isValid(String s) {
            String left = "([{";
            String right = ")]}";
            char[] chararray = s.toCharArray();
            Stack minstack = new Stack();
    
            for (int i = 0; i < chararray.length; i++){
    
                if (minstack.isEmpty() && right.indexOf(chararray[i]) >=0) return false;
    
                if (left.indexOf(chararray[i]) >= 0) minstack.push(chararray[i]);
                else if (left.indexOf((char)minstack.pop()) != right.indexOf(chararray[i])) 
                      return false;
            }
             return minstack.isEmpty();
     }

  • 0
    M

    nice solution !


  • 0
    G

    if you use ascii to check if it is valid ,like this Math.abs(s.charAt(i) - stack.pop()) > 5, you can make your code fewer lines


  • 0
    B

    Sorry, I cannot get this. What does this magic number 5 mean? Could you please explain more?
    And by the way, in real program, doing such a trick will require a detailed COMMENT which will be much longer :)


  • 0
    G

    Same to my solution, hah~


Log in to reply
 

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