leetcode 678. Valid Parenthesis String 有效括号的判断 + 保存index遍历

梦里梦外; 2022-06-03 08:24 97阅读 0赞

Given a string containing only three types of characters: ‘(‘, ‘)’ and ‘\*’, write a function to check whether this string is valid. We define the validity of a string by these rules:

Any left parenthesis ‘(’ must have a corresponding right parenthesis ‘)’.  
Any right parenthesis ‘)’ must have a corresponding left parenthesis ‘(‘.  
Left parenthesis ‘(’ must go before the corresponding right parenthesis ‘)’.  
‘\*’ could be treated as a single right parenthesis ‘)’ or a single left parenthesis ‘(’ or an empty string.  
An empty string is also valid.  
Example 1:  
Input: “()”  
Output: True  
Example 2:  
Input: “(\*)”  
Output: True  
Example 3:  
Input: “(\*))”  
Output: True  
Note:  
The string size will be in the range \[1, 100\].

本题题意很简单，就是多添加了一个\*的处理

建议和[leetcode 32. Longest Valid Parentheses 最长有效括号长度][leetcode 32. Longest Valid Parentheses] 和 [leetcode 20. Valid Parentheses][] 一起学习

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    
    using namespace std;
    
    
    
    class Solution 
    {
    public:
        bool checkValidString(string s)
        {
            stack<int> left, star;
            for (int i = 0; i < s.length(); i++)
            {
                if (s[i] == '*')
                    star.push(i);
                else if (s[i] == '(')
                    left.push(i);
                else
                {
                    if (left.empty() == false)
                        left.pop();
                    else if (star.empty() == false)
                        star.pop();
                    else
                        return false;
                }
            }
    
            while (left.empty() == false && star.empty() == false)
            {
                if (star.top() < left.top())
                    return false;
                else
                {
                    left.pop();
                    star.pop();
                }
            }
            return left.empty() == true;
        }
    };

[leetcode 32. Longest Valid Parentheses]: http://blog.csdn.net/jackzhang_123/article/details/77801969
[leetcode 20. Valid Parentheses]: http://blog.csdn.net/jackzhang_123/article/details/77748997