Skip to content

Latest commit

 

History

History
323 lines (268 loc) · 7.09 KB

File metadata and controls

323 lines (268 loc) · 7.09 KB
comments difficulty edit_url rating source tags
true
简单
1311
第 131 场周赛 Q1
字符串

English Version

题目描述

有效括号字符串为空 """(" + 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 = "(()())(())"
输出:"()()()"
解释:
输入字符串为 "(()())(())",原语化分解得到 "(()())" + "(())",
删除每个部分中的最外层括号后得到 "()()" + "()" = "()()()"。

示例 2:

输入:s = "(()())(())(()(()))"
输出:"()()()()(())"
解释:
输入字符串为 "(()())(())(()(()))",原语化分解得到 "(()())" + "(())" + "(()(()))",
删除每个部分中的最外层括号后得到 "()()" + "()" + "()(())" = "()()()()(())"。

示例 3:

输入:s = "()()"
输出:""
解释:
输入字符串为 "()()",原语化分解得到 "()" + "()",
删除每个部分中的最外层括号后得到 "" + "" = ""。

 

提示:

  • 1 <= s.length <= 105
  • s[i]'('')'
  • s 是一个有效括号字符串

解法

方法一:计数

遍历字符串,遇到左括号 '(' 计数器加一,此时计数器不为 $1$ 时,说明当前括号不是最外层括号,将其加入结果字符串。遇到右括号 ')' 计数器减一,此时计数器不为 $0$ 时,说明当前括号不是最外层括号,将其加入结果字符串。

时间复杂度 $O(n)$,其中 $n$ 为字符串长度。忽略答案字符串的空间开销,空间复杂度 $O(1)$

Python3

class Solution:
    def removeOuterParentheses(self, s: str) -> str:
        ans = []
        cnt = 0
        for c in s:
            if c == '(':
                cnt += 1
                if cnt > 1:
                    ans.append(c)
            else:
                cnt -= 1
                if cnt > 0:
                    ans.append(c)
        return ''.join(ans)

Java

class Solution {
    public String removeOuterParentheses(String s) {
        StringBuilder ans = new StringBuilder();
        int cnt = 0;
        for (int i = 0; i < s.length(); ++i) {
            char c = s.charAt(i);
            if (c == '(') {
                if (++cnt > 1) {
                    ans.append(c);
                }
            } else {
                if (--cnt > 0) {
                    ans.append(c);
                }
            }
        }
        return ans.toString();
    }
}

C++

class Solution {
public:
    string removeOuterParentheses(string s) {
        string ans;
        int cnt = 0;
        for (char& c : s) {
            if (c == '(') {
                if (++cnt > 1) {
                    ans.push_back(c);
                }
            } else {
                if (--cnt) {
                    ans.push_back(c);
                }
            }
        }
        return ans;
    }
};

Go

func removeOuterParentheses(s string) string {
	ans := []rune{}
	cnt := 0
	for _, c := range s {
		if c == '(' {
			cnt++
			if cnt > 1 {
				ans = append(ans, c)
			}
		} else {
			cnt--
			if cnt > 0 {
				ans = append(ans, c)
			}
		}
	}
	return string(ans)
}

TypeScript

function removeOuterParentheses(s: string): string {
    let res = '';
    let depth = 0;
    for (const c of s) {
        if (c === '(') {
            depth++;
        }
        if (depth !== 1) {
            res += c;
        }
        if (c === ')') {
            depth--;
        }
    }
    return res;
}

Rust

impl Solution {
    pub fn remove_outer_parentheses(s: String) -> String {
        let mut res = String::new();
        let mut depth = 0;
        for c in s.chars() {
            if c == '(' {
                depth += 1;
            }
            if depth != 1 {
                res.push(c);
            }
            if c == ')' {
                depth -= 1;
            }
        }
        res
    }
}

方法二

Python3

class Solution:
    def removeOuterParentheses(self, s: str) -> str:
        ans = []
        cnt = 0
        for c in s:
            if c == '(':
                cnt += 1
            if cnt > 1:
                ans.append(c)
            if c == ')':
                cnt -= 1
        return ''.join(ans)

Java

class Solution {
    public String removeOuterParentheses(String s) {
        StringBuilder ans = new StringBuilder();
        int cnt = 0;
        for (int i = 0; i < s.length(); ++i) {
            char c = s.charAt(i);
            if (c == '(') {
                ++cnt;
            }
            if (cnt > 1) {
                ans.append(c);
            }
            if (c == ')') {
                --cnt;
            }
        }
        return ans.toString();
    }
}

C++

class Solution {
public:
    string removeOuterParentheses(string s) {
        string ans;
        int cnt = 0;
        for (char& c : s) {
            if (c == '(') {
                ++cnt;
            }
            if (cnt > 1) {
                ans.push_back(c);
            }
            if (c == ')') {
                --cnt;
            }
        }
        return ans;
    }
};

Go

func removeOuterParentheses(s string) string {
	ans := []rune{}
	cnt := 0
	for _, c := range s {
		if c == '(' {
			cnt++
		}
		if cnt > 1 {
			ans = append(ans, c)
		}
		if c == ')' {
			cnt--
		}
	}
	return string(ans)
}