Parentheses系列

发表于 | 分类于 | 浏览 次

括号系列的几道题，涉及到括号匹配，生成括号等等．

Valid Parentheses

题目链接

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

  1. Open brackets must be closed by the same type of brackets.
  2. Open brackets must be closed in the correct order.

Note that an empty string is also considered valid.

Example 1:

1
2
Input: "()"
Output: true

Example 2:

1
2
Input: "()[]{}"
Output: true

Example 3:

1
2
Input: "(]"
Output: false

Example 4:

1
2
Input: "([)]"
Output: false

Example 5:

1
2
Input: "{[]}"
Output: true

使用一个栈来完成括号的匹配．当遇到一个左括号，入栈；当遇到一个右括号时，查看栈中是否存在对应的左括号．正常的状态是：左右括号的类型和数量都匹配，那么，当整个字符串遍历完成时，栈为空．因此，首先当字符串为空，该字符串必然是valid．若字符串中字符总数为奇数，该字符串必然为invalid．在遍历过程中，如果发现某个右括号不匹配，直接结束遍历过程，并将标记变量改为invalid．遍历结束之后，如果标记变量为valid，此时还需要检查栈是否为空．
代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    bool isValid(string s) {
        if(s.empty()){
            return true;
        }else if(s.size() & 1){
            return false;
        }
        
        // map的初始化
        map<char, char> mp = {
            {'}','{'},{')','('},{']','['}
        };
        stack<char> st;
        bool isValid = true;
        for(int i=0;i<s.size();++i){
            if(s[i] == '[' || s[i] =='(' || s[i] == '{'){
                st.push(s[i]);
            }else if(s[i] == ']' || s[i] == ')' || s[i] == '}'){
                if(!st.empty() && mp[s[i]] == st.top()){
                    st.pop();
                }else{
                    isValid = false;     
                    break;
                }
            }
        }
        if(isValid)
            isValid = st.empty() ? true : false;
        return isValid;
    }
};

时间复杂度：O(n)
空间复杂度：O(1)

Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

1
2
3
4
5
6
7
[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

题目链接

解法1:暴力法

依次枚举每个位置上的字符: 对于任意位置i,先将该位置上的字符设为’(‘,然后继续枚举下一个位置,直到所有位置都被枚举完成,判断形成的字符是否有效.处理完第i位上为’(‘之后,继续枚举第i位上为’)’.只需从第0位开始枚举, 将每个位置上都枚举完成,所有可能的字符串都枚举完成,也找出了所有有效的字符串.显然需要递归实现上述思路.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
bool vaild(string &res) {
    int bal = 0;
    for (int i = 0; i < res.size(); ++i) {
        bal += res[i] == '(' ? 1 : -1;
        if (bal < 0) {
            return false;
        }
    }
    return bal == 0;
}

void generate(string &res, int n) {
    if (res.size() == n * 2) {
        if (vaild(res)) {
            for (auto c : res) {
                cout << c;
            }
            cout << endl;
        }
    } else {
        res.push_back('(');
        generate(res, n);
        res.pop_back();

        res.push_back(')');
        generate(res, n);
        res.pop_back();
    }
}

复杂度分析

  • 时间复杂度
    • 当给出n时, 所有可能的字符串有22 * n个. 这是因为共2 * n 个位置上,每个位置上有两种可能.
    • 对于每一个字符串,枚举该字符串并检查该字符串的有效性的时间复杂度为O(n), 因此总的时间复杂度为O(n* 22 * n)
  • 空间复杂度
    • 如上所示,整个递归过程中,只用了一个string,在这个string中,最多只会存放长度为2n的字符串,因此,空间复杂度为O(n)

解法2: 改进版本

在上述解法中,当已经能够被枚举的字符串无效时仍然继续枚举下一位置,因此浪费了很多时间.例如,对n=1,当位置0上的字符被设为’)’时,无论后续如何枚举,由这个’)’开始的字符串都是无效的.因此,提前退出枚举过程以减少运行时间.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void generate(string &res, int n, int bal, vector<string> &ans) {
    if (res.size() == 2 * n) {
        if (bal == 0) {
            ans.push_back(res);
        }
    } else {
        res.push_back('(');
        generate(res, n, bal + 1, ans);
        res.pop_back();

        // 当我们能确定,被枚举的字符串不可能有效时,提前退出
        // 换言之,只有当我们认为被枚举的字符串可能有效时,才继续枚举
        if (bal > 0) {
            res.push_back(')');
            generate(res, n, bal - 1, ans);
            res.pop_back();
        }
    }
}

解法3: 闭合数

将有效字符串表示为不相交子集的总和.
考虑有效括号序列S的闭包数, 至少存在index>=0, 使得S[0], S[1],…,S[2*index+1]是有效的.显然,每个括号序列都有唯一一个的闭包号.

对于每个闭合数c,起始和结束号位于索引0和2c+1.然后位于1-2\c之间的序列和位于2*c+1和2*n之间的序列都是有效序列.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 生成n对括号的有效序列
vector<string> generate(int n) {
    vector<string> ans;
    string res = "";
    if (n == 0) {
        ans.push_back(res);
    } else {
        for (int i = 0; i < n; ++i) {
            for (string left: generate(i)) {
                for (string right: generate(n - 1 - i)) {
                    string tmp = '(' + left + ')' + right;
                    ans.push_back(tmp);
                }
            }
        }
    }
    return ans;
}

valid Parathesis 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:

  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:

1
2
Input: "()"
Output: True

Example 2:

1
2
Input: "(*)"
Output: True

Example 3:

1
2
Input: "(*))"
Output: True

Note:

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

解法 1:对每个*进行枚举

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
    bool checkValidString(string s) {
        return checkValidStringCore(s, 0);
    }
    bool checkValidStringCore(string& s,int pos){
        if(pos == s.size()){
            return valid(s);
        }
        if(s[pos]=='*'){
            string tmp ="()*";
            for(int j=0;j<tmp.size();++j){
                s[pos] = tmp[j];
                if(checkValidStringCore(s, pos+1)){
                    return true;
                }
            }
            s[pos] = '*';
            return false;
        }else{
            return checkValidStringCore(s, pos+1);
        }
    }
    bool valid(string s){
        int bal = 0;
        for(int i=0;i<s.size();++i){
            if(s[i]=='('){
                ++bal;
            }else if(s[i]==')'){
                --bal;
            }
            if(bal < 0){
                return false;
            }
        }
        return bal == 0;
    }
};

解法2:动态规划

dp[i][j]表示字符串i到j位置上的子串是否有效.
若i>j为空串, dp[i][j]=true
若i == j, dp[i][j]是否有效取决于字符串i位置上的字符是否为*, 即dp[i][j] = (s[i]==’‘)
若i+1==j,则dp[i][j]会在四种情况下有效:
s[i] == ‘(‘ && s[j] == ‘)’
s[i] == ‘(‘ && s[j] == ‘\‘ s[i] == ‘*‘ && s[j] == ‘)’
s[i] == ‘*‘ && s[j] == ‘*‘ 其余情况下为false
若i+1<j
dp[i][j] = true只在一种情况下成立,即存在i<k<=j, s[i]和s[k]满足上述四种情况之一,且dp[i][k]=true && dp[k+1][j]=true

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
bool checkValidString(string s) {
    if (s.empty()) {
        return true;
    }
    vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));
    for (int i = 0; i < s.size(); ++i) {
        if (s[i] == '*') {
            dp[i][i] = true;
        }
        if (i < s.size() - 1 && (s[i] == '(' || s[i] == '*') && (s[i + 1] == ')' || s[i + 1] == '*')) {
            dp[i][i + 1] = true;
        }
    }
    for (int j = 2; j < s.size(); ++j) {
        for (int i = 0; i < s.size() - j; ++i) {
            if (s[i] == '*' && dp[i + 1][i + j]) {
                dp[i][i + j] = true;
            } else if (s[i] == '(' || s[i] == '*') {
                for (int k = i + 1; k <= i + j; ++k) {
                    if ((s[k] == ')' || s[k] == '*')
                        && (k == i + 1 || dp[i + 1][k - 1])
                        && (k == i + j || dp[k + 1][i + j])) {
                        dp[i][i + j] = true;
                        break;
                    }
                }
            }
        }
    }
    return dp[0][s.size() - 1];
}

复杂度分析

  • 时间复杂度：O(n3)
  • 空间复杂度：O(n2)

解法3: 贪心

lo,hi分别表示尚未匹配的左括号的最少和最大数量.尚未匹配的左括号的最少数量在仅把左括号当做左括号时取得.最大数量在把所有*都当做右括号时取得.

  • 当hi<0时,说明即使把所有*都当做左括号也无法满足左括号和右括号之间的匹配关系,因此,此字符串无效.
  • 当hi>0, 而lo<0时,说明将部分*当做左括号才能满足左括号和右括号之间的匹配关系.
  • 当hi>0, 而lo>0时, 说明左括号的数量多于右括号的数量.尚未匹配的左括号的最少数量还是lo.
  • 当hi=0,lo=0时,说明左括号和右括号的数量相等.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool checkValidString(string s) {
    int lo = 0, hi = 0;
    for (auto c: s) {
        lo += c == '(' ? 1 : -1;
        hi += c != ')' ? 1 : -1;
        if (hi < 0) {     // 即使把所有的*号都看作左括号也不行
            return false;
        }

        // 如果将所有*号看做右括号时导致左括号较少，则将部分*号看做左括号
        lo = max(lo, 0);
    }
    return lo == 0;     // 最后需要检查是否左右括号彻底抵消
}

Longest valid parathesis

题目链接

解法1:暴力破解

列举从每个位置开始的子串能够获得的最大长度.若某位置的字符是’)’，则从该位置获取的最大子串长度为0。

1
2
3
4
5
6
7
8
9
10
Example:
"((())"

(( --> invalid
(( --> invalid
() --> valid, length=2
)) --> invalid
((()--> invalid
(())--> valid, length=4
maxlength=4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    int longestValidParentheses(string s) {
        int maxLen = 0;
        for(int i=0;i<s.size();++i){
            for(int j=2;j<=s.size() - i ;j+=2){
                if( isValid(s.substr(i, j))){
                    maxLen = max(maxLen, j);
                }
            }
        }
        return maxLen;
    }
    
    bool isValid(string s){
        stack<char> st;
        for(int i=0;i<s.size();++i){
            if(s[i] == '('){
                st.push('(');
            }else if(!st.empty() && st.top() == '('){
                st.pop();
            }else{
                return false;
            }
        }
        return st.empty();
    }
};

超时。

解法2:动态规划

使用数组dp，dp[i]表示以索引i处的元素结尾的子串中是合法括号串的串的长度。
如果s[i] = ‘(‘，那么以s[i]结尾的子串中是合法括号串的长度为0。因为合法的括号串不会以’(‘结尾。具体过程参考这里
如果s[i] = ‘)’，

  • 如果s[i-1] = ‘(‘，那么dp[i] = dp[i-2] + 2
  • 如果s[i-1] = ‘)’，并且s[i - dp[i-1] - 1] = ‘(‘，那么
    dp[i] = dp[i - 1] + dp[i - dp[i-1] - 2] + 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int longestValidParentheses(string s) {
        vector<int> dp(s.size(), 0);
        int res = 0;
        for(int i=1;i<s.size();++i){
            if(s[i] == ')'){
                if(s[i-1] == '('){
                    dp[i] = (i >= 2 ? dp[i-2] : 0) + 2 ;
                }else if(s[i-1] == ')'){
                    if((i-dp[i-1] - 1 >= 0) && s[i-dp[i-1] - 1] == '('){
                        dp[i] = dp[i-1] + ((i - dp[i-1]) >= 2 ? dp[i - dp[i-1] - 2] : 0) + 2;
                    }
                }
            }
            res = max(res, dp[i]);
        }
        return res;
    }
};

时间复杂度：O(n)
空间复杂度：O(n)

解法3:使用栈

与其找出每个可能的子串并检查它的正确性，我们可以利用栈来

Score of Parentheses

如何区分以位置j结尾的子问题和以位置开始的子问题

Given a balanced parentheses string S, compute the score of the string based on the following rule:

  • () has score 1
  • AB has score A + B, where A and B are balanced parentheses strings.
  • (A) has score 2 * A, where A is a balanced parentheses string.

Example 1:

1
2
Input: "()"
Output: 1

Example 2:

1
2
Input: "(())"
Output: 2

Example 3:

1
2
Input: "()()"
Output: 2

Example 4:

1
2
Input: "(()(()))"
Output: 6

Note:

  1. S is a balanced parentheses string, containing only ( and ).
  2. 2 <= S.length <= 50

解法1:分而治之

首先把整个字符串S分成多个子串s1, s2, …,sn.score(S) = score(s1)+score(s1)+…+score(sn)

接下来,计算每个子串si>的分数,子串si有两种可能:

  • 长度为2: score(si)=1
  • 长度大于2:score(si) = 2 * score(si[1:n-1])(假设n为si.size())

重点是从位置i到位置j中间的某个位置k，能够形成一个子串，这个子串是一个valid string

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    int scoreOfParentheses(string S) {
        if(S.empty()){
            return 0;
        }
        return scoreOfParenthesesCore(S, 0, S.size()-1);
    }
    int scoreOfParenthesesCore(string s, int lo, int hi){
        int ans = 0, bal = 0;
        
        for(int k=lo;k<=hi;++k){
            bal += s[k] == '(' ? 1 : -1;
            if(bal == 0){
                if(k - lo == 1){
                    ans++;
                }else{
                    ans += 2 * scoreOfParenthesesCore(s, lo + 1, k - 1);
                }
                lo = k + 1;
            }
        }
        
        return ans;
    }
};

解法２栈

解法3count cores