Sunday, April 19, 2015

Valid Paranthesis

Problem:
Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.


Solution:
class Solution {
public:
    bool isValid(string s) {
        stack<char> tmp;
        int size = s.size();
        
        for (int i = 0; i < size; i++) {
            if (s[i] == '(' || s[i] == '{' || s[i] == '[')
                tmp.push(s[i]);
            else if (s[i] == ')') {
                if (tmp.empty() || tmp.top() != '(')
                    return false;
                tmp.pop();
            } else if (s[i] == '}') {
                if (tmp.empty() || tmp.top() !=  '{')
                    return false;
                tmp.pop();
            } else if (s[i] == ']') {
                if (tmp.empty() || tmp.top() !=  '[')
                    return false;
                tmp.pop();
            }
        }
        // Assuming empty string returns true;
        if (tmp.empty())
            return true;
        return false;
    }
};

No comments:

Post a Comment