首页 > 编程语言 > 详细

LeetCode 678. Valid Parenthesis String 有效的括号字符串 (C++/Java)

时间:2020-02-22 23:59:31      阅读:109      评论:0      收藏: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:

  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:

Input: "()"
Output: True

 

Example 2:

Input: "(*)"
Output: True

 

Example 3:

Input: "(*))"
Output: True

分析:

括号匹配,左括号和右括号必须对应上,且左括号在右括号前面,*号可以当任意的左括号右括号或者是空。

首先可以利用动态规划,求解dp[i][j],其中i,j表示字符串的字串范围,为1表示可以匹配上,0表示不能匹配上。当i等于j是,也就是一个字符,只有当时‘*’的时候才能匹配,那如果s[i]是*或者是左括号,s[j]是*或者右括号,且dp[i+1][j-1]是成功匹配的,那么dp[i][j]也是匹配的。否则就要在i到j之间寻找一个分割点k使得i到k,k+1到j之间的字符串是匹配的。

那还可以利用计数法,设置两个变量,一个记录当前需要匹配的最小左括号数,和一个当前需要匹配最大左括号数。

遍历字符串,当前字符为左括号时,意味着我们必须要匹配一个左括号,所以最小左括号数+1,其他情况最小左括号数减一,因为*可以当成右括号,消掉一个左括号。

当前字符为右括号时,意味着我们必须要匹配一个右括号,此时最大左括号数-1,其他情况最大左括号数+1,因为*可以当成左括号,增加一个最大的左括号数。

当最大左括号数小于0时,代表已经有右括号没有相应的左括号或者*和它匹配了,如果最小左括号数小于0,则重新将它置为0,因为最小左括号数小于0的情况时发生在有多个*出现,我们把*当成空,所以置其为0.最后如果最小括号数为0的话,就代表匹配成功了。

程序:

C++

class Solution {
public:
    bool checkValidString(string s) {
        int n = s.length();
        if(n == 0) return true;
        dp = vector<vector<int>>(n, vector<int>(n, -1));
        return checkValid(s, 0, n-1);
    }
private:
    vector<vector<int>> dp;
    bool checkValid(string& s, int i, int j){
        if(i > j)
            return true;
        if(dp[i][j] >= 0)
            return dp[i][j];
        if(i == j){
            if(s[i] == *){
                return dp[i][j] = 1;
            }
            else{
                return dp[i][j] = 0;
            }
        }
        if((s[i] == * || s[i] == () && (s[j] == * || s[j] == )) && checkValid(s, i+1, j-1)){
            return dp[i][j] = 1;
        }
        for(int k = i; k < j; ++k){
            if(checkValid(s, i, k) && checkValid(s, k+1, j)){
                return dp[i][j] = 1;
            }
        }
        return dp[i][j] = 0;
    }
};

Java

class Solution {
    public boolean checkValidString(String s) {
        char[] str = s.toCharArray();
        if(str.length == 0) return true;
        int min_op = 0;
        int max_op = 0;
        for(char ch:str){
            if(ch == ‘(‘){
                min_op++;
            }else{
                min_op--;
            }
            if(ch == ‘)‘){
                max_op--;
            }else{
                max_op++;
            }
            if (max_op < 0) return false;
            min_op = Math.max(0, min_op);
        }
        if(min_op == 0)
            return true;
        else
            return false;
    }
}

 

LeetCode 678. Valid Parenthesis String 有效的括号字符串 (C++/Java)

原文:https://www.cnblogs.com/silentteller/p/12348010.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!