题解45 | 发现个懒得用栈的方法#合法的括号字符串#

注意区别于多种括号（[{}]）：题解28 | 知否知否，应是栈空字走#有效括号序列#

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return bool布尔型
     */
    bool isValidString(string s) {
        // write code here
        int braket;
        braket = 0;
        for(int i = 0; i < s.size(); i++){
            if(s[i] == ')'){
                braket--;
                if (braket < 0) {
                    return false;
                }
            }
            else {
                braket++;
            }
        }
        
        braket = 0;
        for(int i = s.size()-1; i >=0 ; i--){
            if(s[i] == '('){
                braket--;
                if (braket < 0) {
                    return false;
                }
            }
            else {
                braket++;
            }
        }
        return true;
    }

};

基本算法思想：

该算法通过遍历字符串，使用一个变量记录括号的数量。

遇到左括号时，数量加1；遇到右括号时，数量减1。如果数量小于0，说明右括号比左括号多，返回false。

遍历完字符串后，再次遍历字符串，但这一次从末尾开始遍历，使用一个变量记录括号的数量。

遇到右括号时，数量加1；遇到左括号时，数量减1。如果数量小于0，说明左括号比右括号多，返回false。

如果遍历完字符串后，数量仍为0，说明左右括号数量相等，返回true；否则返回false。

时间复杂度：O(n)，其中n为字符串的长度。需要遍历两次字符串。

空间复杂度：O(1)，只需要使用常数个额外变量。