p29 有效的括号 (leetcode 20)

//Time:O(n),Space:O(n)
class Solution
{
public:
    bool match(char a, char b)
    {
        return ((a==‘(‘)&&(b==‘)‘)) ||
            ((a==‘[‘)&&(b==‘]‘)) ||
            ((a==‘{‘)&&(b==‘}‘));
    }

    bool isValid(string s)
    {
        stack<char> stack;

        if (s.size() == 0) return true;

        for (int i = 0; i < s.size(); i++)
        {
            if ((s[i] == ‘(‘) || (s[i] == ‘[‘) || (s[i] == ‘{‘))
            {
                stack.push(s[i]);
            }
            else if ((s[i] == ‘)‘) || (s[i] == ‘]‘) || (s[i] == ‘}‘))
            {
                if ((!stack.empty()) && (match(stack.top(),s[i])))
                {
                    stack.pop();
                }
                else
                {
                    return false;
                }
            }
        }

        return stack.empty();
    }
};

class Solution
{
    public boolean match(char a,char b)
    {
        return ((a==‘(‘)&&(b==‘)‘))||
                ((a==‘[‘)&&(b==‘]‘))||
                ((a==‘{‘)&&(b==‘}‘));
    }
    
    public boolean isValid(String s)
    {
        Stack<Character> stack=new Stack<>();

        if (s.length() == 0) return true;

        for (int i = 0; i < s.length(); i++)
        {
            if ((s.charAt(i) == ‘(‘) || (s.charAt(i) == ‘[‘) || (s.charAt(i) == ‘{‘))
            {
                stack.push(s.charAt(i));
            }
            else if ((s.charAt(i) == ‘)‘) || (s.charAt(i) == ‘]‘) || (s.charAt(i) == ‘}‘))
            {
                if ((!stack.isEmpty()) && (match(stack.peek(),s.charAt(i))))
                {
                    stack.pop();
                }
                else
                {
                    return false;
                }
            }
        }

        return stack.isEmpty();
    }
};