[LeetCode] 678. Valid Parenthesis String 验证括号字符串

2021年09月15日 阅读数:4
这篇文章主要向大家介绍[LeetCode] 678. Valid Parenthesis String 验证括号字符串,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

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:html

  1. Any left parenthesis '(' must have a corresponding right parenthesis ')'.
  2. Any right parenthesis ')' must have a corresponding left parenthesis '('.
  3. Left parenthesis '(' must go before the corresponding right parenthesis ')'.
  4. '*' could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string.
  5. An empty string is also valid.

Example 1:java

Input: "()"
Output: True

Example 2:python

Input: "(*)"
Output: True

Example 3:post

Input: "(*))"
Output: True

Note:this

  1. The string size will be in the range [1, 100].

判断给定的字符串的括号匹配是否合法, 20. Valid Parentheses 的变形,这题里只有小括号'()'和*,*号能够表明'(', ')'或者至关于没有。url

解法1: 迭代code

解法2: 递归,最容易想到的解法,用一个变量cnt记录左括号的数量,当遇到*号时分为三种状况递归下去。Python TLE,  C++: 1148 mshtm

解法2: 最优解法,设两个变量cmin和cmax,cmin最少左括号的状况,cmax表示最多左括号的状况,其它状况在[cmin, cmax]之间。遍历字符串,遇到左括号时,cmin和cmax都自增1;当遇到右括号时,当cmin大于0时,cmin才自减1,不然保持为0(由于其它*状况可能会平衡掉),而cmax减1;当遇到星号时,当cmin大于0时,cmin才自减1(看成右括号),而cmax自增1(看成左括号)。若是cmax小于0,说明到此字符时前面的右括号太多,有*也没法平衡掉,返回false。当循环结束后,返回cmin是否为0。blog

Java:递归

public boolean checkValidString(String s) {
        int low = 0;
        int high = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                low++;
                high++;
            } else if (s.charAt(i) == ')') {
                if (low > 0) {
                    low--;
                }
                high--;
            } else {
                if (low > 0) {
                    low--;
                }
                high++;
            }
            if (high < 0) {
                return false;
            }
        }
        return low == 0;
    }

Python:

class Solution(object):
    def checkValidString(self, s):
        """
        :type s: str
        :rtype: bool
        """
        lower, upper = 0, 0  # keep lower bound and upper bound of '(' counts
        for c in s:
            lower += 1 if c == '(' else -1
            upper -= 1 if c == ')' else -1
            if upper < 0: break
            lower = max(lower, 0)
        return lower == 0  # range of '(' count is valid  

Python:

def checkValidString(self, s):
        cmin = cmax = 0
        for i in s:
            if i == '(':
                cmax += 1
                cmin += 1
            if i == ')':
                cmax -= 1
                cmin = max(cmin - 1, 0)
            if i == '*':
                cmax += 1
                cmin = max(cmin - 1, 0)
            if cmax < 0:
                return False
        return cmin == 0

Python:

def checkValidString(self, s):
        cmin = cmax = 0
        for i in s:
            cmax = cmax-1 if i==')' else cmax+1
            cmin = cmin+1 if i=='(' else max(cmin - 1, 0) 
            if cmax < 0: return False
        return cmin == 0 

Python: TLE

class Solution(object):
    def checkValidString(self, s):
        """
        :type s: str
        :rtype: bool
        """
        return self.helper(s, 0)
        
    def helper(self, s, count):
        # if not s:
        #     return count == 0
        if count < 0:
            return False

        for i in xrange(len(s)):
            if s[i] == '(':
                count += 1
            elif s[i] == ')':
                if count <= 0:
                    return False
                else:
                    count -= 1
            else:
                return self.helper(s[i+1:], count+1)  or \
                       self.helper(s[i+1:], count)  or \
                       self.helper(s[i+1:], count-1) 
            
        return count == 0    

    
if __name__ == '__main__':
    print Solution().checkValidString("(((((*(()((((*((**(((()()*)()()()*((((**)())*)*)))))))(())(()))())((*()()(((()((()*(())*(()**)()(())")  

C++:

class Solution {
public:
    bool checkValidString(string s) {
        stack<int> left, star;
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] == '*') star.push(i);
            else if (s[i] == '(') left.push(i);
            else {
                if (left.empty() && star.empty()) return false;
                if (!left.empty()) left.pop();
                else star.pop();
            }
        }
        while (!left.empty() && !star.empty()) {
            if (left.top() > star.top()) return false;
            left.pop(); star.pop();
        }
        return left.empty();
    }
};

C++:

class Solution {
public:
    bool checkValidString(string s) {
        return helper(s, 0, 0);
    }
    bool helper(string s, int start, int cnt) {
        if (cnt < 0) return false;
        for (int i = start; i < s.size(); ++i) {
            if (s[i] == '(') {
                ++cnt;
            } else if (s[i] == ')') {
                if (cnt <= 0) return false;
                --cnt;
            } else {
                return helper(s, i + 1, cnt) || helper(s, i + 1, cnt + 1) || helper(s, i + 1, cnt - 1);
            }
        }
        return cnt == 0;
    }
};

C++:

class Solution {
public:
    bool checkValidString(string s) {
        int low = 0, high = 0;
        for (char c : s) {
            if (c == '(') {
                ++low; ++high;
            } else if (c == ')') {
                if (low > 0) --low;
                --high;
            } else {
                if (low > 0) --low;
                ++high;
            }
            if (high < 0) return false;
        }
        return low == 0;
    }
};

  

  

相似题目:  

[LeetCode] 20. Valid Parentheses 合法括号

 

  

 

All LeetCode Questions List 题目汇总