Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1021.html
1021. Remove Outermost Parentheses (Easy)
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
.
Example 1:
Input: "(()())(())" Output: "()()()" Explanation: The input string is "(()())(())", with primitive decomposition "(()())" + "(())". After removing outer parentheses of each part, this is "()()" + "()" = "()()()".
Example 2:
Input: "(()())(())(()(()))" Output: "()()()()(())" Explanation: The input string is "(()())(())(()(()))", with primitive decomposition "(()())" + "(())" + "(()(()))". After removing outer parentheses of each part, this is "()()" + "()" + "()(())" = "()()()()(())".
Example 3:
Input: "()()" Output: "" Explanation: The input string is "()()", with primitive decomposition "()" + "()". After removing outer parentheses of each part, this is "" + "" = "".
Note:
S.length <= 10000
S[i]
is"("
or")"
S
is a valid parentheses string
Companies:
Google
Related Topics:
Stack
Solution 1.
-
class Solution { public String removeOuterParentheses(String S) { List<Integer> indices = new ArrayList<Integer>(); Stack<Character> stack = new Stack<Character>(); int length = S.length(); int begin = 0; for (int i = 0; i < length; i++) { char c = S.charAt(i); if (c == '(') stack.push(c); else { stack.pop(); if (stack.isEmpty()) { indices.add(begin); indices.add(i); begin = i + 1; } } } StringBuffer sb = new StringBuffer(); for (int i = 0; i < length; i++) { if (!indices.contains(i)) sb.append(S.charAt(i)); } return sb.toString(); } } ############ 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(); } }
-
// OJ: https://leetcode.com/problems/remove-outermost-parentheses/ // Time: O(N) // Space: O(1) class Solution { public: string removeOuterParentheses(string S) { string ans; int cnt = 0, start = 0; for (int i = 0; i < S.size(); ++i) { if (S[i] == '(') ++cnt; else if (--cnt == 0) { ans += S.substr(start + 1, i - start - 1); start = i + 1; } } return ans; } };
-
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) ############ class Solution(object): def maxScoreSightseeingPair(self, A): """ :type A: List[int] :rtype: int """ pre_i = 0 res = 0 for j in range(1, len(A)): res = max(A[j] - j + A[pre_i] + pre_i, res) if A[j] + j > A[pre_i] + pre_i: pre_i = j return res
-
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) }
-
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; }
-
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 } }