C++ 将括号序列分割为最大有效子字符串

在这个问题中，我们需要将括号字符串分割成有效的组。当所有左括号有相应的右括号时，我们可以说这组括号是有效的。

问题陈述 - 我们给定一个包含开括号和闭括号的字符串。我们需要将字符串分割以得到最大有效的括号字符串。

示例示例

输入

par = "(())()(()())"

输出

(()), (), (()()),

说明 - 每个子字符串包含有效的括号序列。

输入

par = "()()"

输出：

(), ()

解释 - 我们将字符串分成两组。

输入

par = "()(())"

输出

(), (())

方法1

我们将遍历字符串，并且如果在任何索引处开括号和闭括号的数量相同，则打印前一个子字符串并开始一个新的子字符串。

算法

步骤1 - 初始化’open’和’close’为0，以存储到达特定索引处的开括号和闭括号的数量。同时，定义字符串列表以存储有效的组合。

步骤2 - 如果字符串长度为0，则返回一个空列表。

步骤3 - 遍历给定的字符串。

步骤4 - 将当前字符追加到’temp’字符串。

步骤5 - 如果当前字符是'(‘，则将’open’增加1。否则，将’close’增加1。

步骤6 - 如果open和close的值相同，则将temp字符串添加到’ans’列表中。

步骤7 - 返回’ans’列表。

步骤8 - 在main()方法中，遍历有效序列的列表，并打印所有序列。

示例

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

vector<string> getBalancedGroups(string par) {
   vector<string> ans;
   // To store a number of open and closed brackets
   int open = 0;
   int close = 0;
   // To store a valid group of parenthesis
   string temp = "";
   int len = par.size();
   // Return the same string if it is empty
   if (len == 0)
     return ans;

   // Finding valid groups
   for (int p = 0; p < len; p++) {
      temp += par[p];
      // For opening braces
      if (par[p] == '(') {
         open++;
      }
      // For closing braces
      if (par[p] == ')') {
         close++;
      }
      // When we get a valid group, push it to the 'ans' list.
      if (open == close) {
        ans.push_back(temp);
        temp = "";
      }
   }
   return ans;
}

int main() {
   string par = "(())()(()())";
   vector<string> balancedGroup;
   balancedGroup = getBalancedGroups(par);
   cout << "The valid groups of parenthesis are - ";
   // printing the balanced groups
   for (auto group : balancedGroup)
     cout << group << ", ";
   return 0;
}

输出

The valid groups of parenthesis are - (()), (), (()()),

时间复杂度 – O(N) 沿字符串遍历。

空间复杂度 – O(N) 存储有效子序列。

我们学会了在此问题中找到有效的括号序列。我们使用的逻辑是，当每个开括号对应一个闭括号时，我们可以说它是一个有效的子序列并拆分字符串。