Remove Outermost Parentheses

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: "()()()"

Approach

Java


import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class RemoveOutermostParentheses {
    public static void main(String[] args) {
        String str = "(()())(())";
        System.out.println(removeOuterParentheses(str));
    }

    // function to remove outer parentheses
    // from the string
    static String removeOuterParentheses(String S) {
        Stack<Characterst = new Stack<Character>();
        int n = S.length();
        List<Stringres = new ArrayList<String>();
        String str = "";

        // iterate till the length of
        // the string
        for (int i = 0; i < n; i++) {

            // if open bracket then
            // push into the stack
            // and append into the new string
            if (S.charAt(i) == '(') {
                st.push(S.charAt(i));
                str += S.charAt(i);
            }

            // if closing bracket then pop
            // from the stack and add the current
            // into the new string
            else {
                st.pop();
                str += S.charAt(i);

                // if stack is empty
                // then reset str
                if (st.isEmpty()) {
                    res.add(str);
                    str = "";
                }
            }
        }
        String ans = "";
        for (int i = 0; i < res.size(); i++) {
            String x = res.get(i);
            for (int j = 1; j < x.length() - 1; j++)
                ans += x.charAt(j);
        }
        return ans;
    }
}

C++

#include <bits/stdc++.h>
using namespace std;


//function to remove outer parentheses
//from the string
string removeOuterParentheses(string S)
{
    stack<charst;
    int n = S.size();
    vector<stringres;
    string str = "";

    //iterate till the length of
    //the string
    for (int i = 0i < ni++)
    {

        //if open bracket then 
        //push into the stack
        //and append into the new string
        if (S[i] == '(')
        {
            st.push(S[i]);
            str += S[i];
        }

        //if closing bracket then pop 
        //from the stack and add the current
        //into the new string
        else
        {
            st.pop();
            str += S[i];

            //if stack is empty 
            //then reset str
            if (st.empty())
            {
                res.push_back(str);
                str = "";
            }
        }
    }
    string ans = "";
    for (int i = 0i < res.size(); i++)
    {
        string x = res[i];
        for (int j = 1j < x.size() - 1j++)
            ans += x[j];
    }
    return ans;
}

int main()
{
    string str = "(()())(())";
    cout << removeOuterParentheses(str);
    return 0;
}


No comments:

Post a Comment