题解 | #合法的括号字符串#

合法的括号字符串

http://www.nowcoder.com/practice/eceb50e041ec40bd93240b8b3b62d221

题目分析

题目给出一个字符串，其组成字符种类只包含(，)，*三种

对于该括号字符串，*可以任意表示三种含义的一种，即左括号，右括号，空字符三种含义任一皆可

题目要求我们判断是否该字符串是一个合法的左右括号关系正确的字符串，也就是说出现一个左括号必须在其右侧有对应的右括号，其中星号可以根据情况任意理解转义

返回字符串的合法与否true还是false结果

方法一：栈

实现思路
- 我们维护左括号的下标栈left和星号的下标栈star
- 遍历字符串时，如果遇到左括号则将对应的下标入到left栈，星号栈同理
- 如果遇到右括号则首先在left栈中匹配，即left栈顶元素出栈；如果left栈空，则顺位到star栈出栈；如果star栈也空了，则说明仍有右括号无法匹配，则返回false结果
- 如果上一过程顺利完成，则还需要判断是否有多余的左括号无法匹配：则依次对left栈顶进行判断，如果left栈空了说明所有左括号已经匹配完成；如果left栈非空，则判断star栈中栈顶是否存在下标大于left栈顶的元素，因为只有这样才能对左括号进行匹配；否则返回false结果
- 最终剩余的结果就是true

alt

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return bool布尔型
     */
    bool isValidString(string s) {
        // write code here
        stack<int> left;
        stack<int> star;
        for(int i = 0; i < s.size(); i++) {                        // 处理右括号的匹配
            char c = s[i];
            if(c == '(') left.push(i);                             // 左括号下标入栈
            else if(c == '*') star.push(i);                        // 星号下标入栈
            else {
                if(!left.empty()) left.pop();
                else if(!star.empty()) star.pop();
                else return false;                                 // 右括号数量多则直接返回false
            }
        }
        while(!left.empty()) {                    // 处理多的左括号的匹配
            if(!star.empty() && left.top() < star.top()) {
                left.pop();
                star.pop();
            }
            else return false;                    // 左括号数量多则直接返回false
        }
        return true;
    }
};

复杂度分析

时间复杂度： $O (n)$ ，其中 $n$ 代表字符串的长度，因为遍历的时间代价是 $O (n)$ 的，复杂度跟遍历代价成线性关系。
空间复杂度： $O (n)$ ，栈的空间的代价。

方法二：贪心

实现思路
- 题目中唯一存在可以多义的字符为*，我们用贪心的思想进行最大限度的匹配。
- 从左往右遍历字符串，将所有*视为(，最大化左括号的数量。遍历过程中如果出现右括号的数量多于左括号+星号的数量，则说明该字符串一定不合法，否则该字符串可能合法，需要进一步判断
- 从右往左遍历字符串，将所有*视为)，最大化右括号的数量。遍历过程中如果出现左括号的数量多于右括号+星号的数量，则说明该字符串一定不合法，否则，基于上一步的判断，两种不合法的情况已经全部排除，最终剩下结果只能是合法结果。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return bool布尔型
     */
    bool isValidString(string s) {
        // write code here
        int lc = 0;
        int sc = 0;
        int rc = 0;
        for(int i = 0; i < s.size(); i++) {            // 从左往右遍历计数三个字符出现次数
            char c = s[i];
            if(c == '(') lc++;
            else if(c == ')') rc++;
            else sc++;
            if(lc + sc < rc) return false;             // 只要过程中出现右括号比左括号+星号多则返回false
        }
        lc = sc = rc = 0;
        for(int i = s.size() - 1; i >= 0; i--) {       // 从右往左遍历计数三个字符出现次数
            char c = s[i];
            if(c == ')') rc++;
            else if(c == '(') lc++;
            else sc++;
            if(rc + sc < lc) return false;             // 只要过程中出现左括号比右括号+星号多则返回false
        }
        
        return true;
    }
};