[LeetCode] 1021. Remove Outermost Parentheses

发表于 Disqus：

LeetCode 1021. Remove Outermost Parentheses (删除最外层的括号) Diffculty: Eazy

Question

A valid parentheses string is either empty (""), "(" + A + ")", or A + B, where A and B are valid parentheses strings, and + represents string concatenation. For example, "", "()", "(())()", and "(()(()))" are all valid parentheses strings.

A valid parentheses string S is primitive if it is nonempty, and there does not exist a way to split it into S = A + B, with A and B nonempty valid parentheses strings.

Given a valid parentheses string S, consider its primitive decomposition: S = P_1 + P_2 + ... + P_k, where P_i are primitive valid parentheses strings.

Return S after removing the outermost parentheses of every primitive string in the primitive decomposition of S.

Note:

  1. S.length <= 10000
  2. S[i] is "(" or ")"
  3. S is a valid parentheses string

有效括号字符串为空 ("")、"(" + A + ")" 或 A + B，其中 A 和 B 都是有效的括号字符串，+ 代表字符串的连接。例如，""，"()"，"(())()" 和 "(()(()))" 都是有效的括号字符串。

如果有效字符串 S 非空，且不存在将其拆分为 S = A + B 的方法，我们称其为原语（primitive），其中 A 和 B 都是非空有效括号字符串。

给出一个非空有效字符串 S，考虑将其进行原语化分解，使得：S = P_1 + P_2 + ... + P_k，其中 P_i 是有效括号字符串原语。

对 S 进行原语化分解，删除分解中每个原语字符串的最外层括号，返回 S。

提示：

  1. S.length <= 10000
  2. S[i] 为 "(" 或 ")"
  3. S 是一个有效括号字符串

Example

Example 1

1
2
3
4
5
6
7
8
Input: "(()())(())"
Output: "()()()"

Explanation: 
The input string is "(()())(())", with primitive decomposition "(()())" + "(())".
After removing outer parentheses of each part, this is "()()" + "()" = "()()()".
输入字符串为 "(()())(())"，原语化分解得到 "(()())" + "(())"，
删除每个部分中的最外层括号后得到 "()()" + "()" = "()()()"。

Example 2

1
2
3
4
5
6
7
8
Input: "(()())(())(()(()))"
Output: "()()()()(())"

Explanation: 
The input string is "(()())(())(()(()))", with primitive decomposition "(()())" + "(())" + "(()(()))".
After removing outer parentheses of each part, this is "()()" + "()" + "()(())" = "()()()()(())".
输入字符串为 "(()())(())(()(()))"，原语化分解得到 "(()())" + "(())" + "(()(()))"，
删除每隔部分中的最外层括号后得到 "()()" + "()" + "()(())" = "()()()()(())"。

Example 3

1
2
3
4
5
6
7
8
Input: "()()"
Output: ""

Explanation: 
The input string is "()()", with primitive decomposition "()" + "()".
After removing outer parentheses of each part, this is "" + "" = "".
输入字符串为 "()()"，原语化分解得到 "()" + "()"，
删除每个部分中的最外层括号后得到 "" + "" = ""。

Solution

题意分析

  • Input：一个有效括号字符串 S
  • Output：原语化分解，删除分解中每个原语字符串的最外层括号的 S

Java

My Solution 1: Loop

解题思路

将字符串 S 转为字符数组（char[]），遍历判断字符是 ( 或 )。是 ( 则计数 +1，是 ) 则计数 -1。如计数为 0，则表示一个有效的括号字符串的结束，以此截出有效的括号字符串，去除首尾的括号后，加到结果中。

解题步骤
  1. 定义输出变量（StringBuilder） -> result
  2. 定义临时存储变量（StringBuilder） -> temp
  3. 定义计数变量（int） -> num
  4. 将字符串 S 转为字符数组 -> s
  5. 循环字符数组 s -> c
    1. 将字符 c 存到临时变量 temp 中
    2. 判断字符是 ( 或 )。是 ( 则计数 num++，是 ) 则计数 num--
    3. 判断 num 是否为 0，如为 0，则去除 temp 首尾的括号后，加到 result 中，并重新初始化 temp
  6. 循环结束后，返回结果变量 -> result.toString()
Code
初版
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
public String removeOuterParentheses(String S) {
    StringBuilder result = new StringBuilder();
    StringBuilder temp = new StringBuilder();

    int num = 0;
    char[] s = S.toCharArray();
    for (char c : s) {
        temp.append(String.valueOf(c));

        if (c == '(') {
            num++;
        }

        if (c == ')') {
            num--;
        }

        if (num == 0) {
            temp.replace(0, 1, "");
            temp.replace(temp.length() - 1, temp.length(), "");
            result.append(temp);
            temp = new StringBuilder();
        }
    }
    return result.toString();
}
优化版
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public String removeOuterParentheses(String S) {
    StringBuilder result = new StringBuilder();

    int num = 0;
    for (char c : S.toCharArray()) {
        if (c == '(') {
            num++;
        }

        if (num > 1) {
            result.append(String.valueOf(c));
        }

        if (c == ')') {
            num--;
        }
    }
    return result.toString();
}
Complexity Analysis
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(n)$

LeetCode Discuss Solution 1: Loop

Code
1
2
3
4
5
6
7
8
9
public String removeOuterParentheses(String S) {
    StringBuilder s = new StringBuilder();
    int opened = 0;
    for (char c : S.toCharArray()) {
        if (c == '(' && opened++ > 0) s.append(c);
        if (c == ')' && opened-- > 1) s.append(c);
    }
    return s.toString();
}
Complexity Analysis
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(n)$
解题思路

与我的解决思路差不多，代码更简洁。

LeetCode Discuss Solution 2: Stack

Code
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
public String removeOuterParentheses(String s) {
    Stack<Character> stack = new Stack<>();

    String result = "";
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);

        if (stack.isEmpty() && c == '(') {
            stack.push(c);
            continue;
        }

        if (stack.size() == 1 && c == ')') {
            stack.pop();
            continue;
        }

        if (c == '(') {
            stack.push(c);
        }

        if (c == ')') {
            stack.pop();
        }
        result += c + "";
    }

    return result;
}
Complexity Analysis
  • 时间复杂度：$O(n)$
  • 空间复杂度：
解题思路

利用堆栈（Stack）的先进后出，后进先出的原理。遇到 ( 就进栈，遇到 ) 就出栈。

Summary

这个问题的难点在于如何原语化分解字符串（即最外层的每一个 () 或 ((XX)(XX))）或者说如何确认 ( or ) 是需要被删除的。

就需要利用 ( 或 ) 是成对出现的这点，( 必定有一个 )，(( 必定有一个 ))。

以上的两种解题思路其实是相似的，区别只在于一个是使用自增自减的方式判断原语，另一个是利用堆栈的先进后出的方式判断原语。

References