LeetCode刷题笔记（Valid Parentheses）

最近转移战线，开始准备进攻队列、栈和优先队列等相关的题目了。今天刷了一道与栈相关的题目，下面来分享一下经验吧！

题目如下：

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Note that an empty string is also considered valid.

Example 1:

Input: "()"
Output: true
Example 2:

Input: "()[]{}"
Output: true
Example 3:

Input: "(]"
Output: false
Example 4:

Input: "([)]"
Output: false
Example 5:

Input: "{[]}"
Output: true

题意分析：

给定一个仅包含'(', ')', '{', '}', '[' 和 ']'字符的字符串，确定该字符串是否是有效的字符串。

有效字符串满足：

①必须使用相同类型的左括号和右括号。

②必须以正确的顺序排放左括号和右括号。

解答如下：

方法一（堆栈法+字符转换）

先创建一个堆栈，将先出现的左括号用堆栈一一的压进去，然后当遇到右括号时，再用栈顶的左括号与之进行匹配，若匹配不上则返回false，若堆栈中的左括号均匹配上了且没有多余的右括号，则返回true。

class Solution{
public:
    bool isValid( string s ){

        stack<char> stack;             //创建一个堆栈
        for ( int i = 0; i < s.size(); i++ ) {
            if( s[i] == '(' || s[i] == '[' || s[i] == '{' )
                stack.push( s[i] );
            else {
                if( stack.empty() )    //防止有单独的右括号
                    return false;
                char m = stack.top();
                stack.pop();
                char match;
                if ( s[i] == ')')      //由于左右括号本不相等，所以必须要借助中间字符转换之
                    match = '(';
                else if ( s[i] == ']')
                    match = '[';
                else
                { assert(s[i] == '}');
                    match = '{';}
                if ( m != match )
                    return false;
            }
        }
        if ( !stack.empty() )           //当所有左右括号都匹配上了，且没有单独的左括号，则返回true
            return false;
        return true;
    }
};

提交后的结果如下：

LeetCode刷题笔记（Valid Parentheses）

方法二（堆栈法+不字符转换）

在方法一的基础上，无须新建m和match字符变量直接进行判断，从而优化了代码。

class Solution{
public:
    bool isValid( string s ){

        stack<char> stack;
        for ( int i = 0; i < s.size(); i++ ) {
            if( s[i] == '(' || s[i] == '[' || s[i] == '{' ) stack.push( s[i] );
            else {
                if( stack.empty() ) return false;
                if( s[i] == ')' && stack.top() != '(' ) return false;   //直接进行匹配
                if( s[i] == ']' && stack.top() != '[' ) return false;   //直接进行匹配
                if( s[i] == '}' && stack.top() != '{' ) return false;   //直接进行匹配
                stack.pop();
            }
        }
        return stack.empty();                                           //省去了判断              
    }
};

提交后的结果如下：

LeetCode刷题笔记（Valid Parentheses）

日积月累，与君共进，增增小结，未完待续。

LeetCode刷题笔记（Valid Parentheses）

相关推荐