数据结构
网络
关系型数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究将括号序列拆分为最大有效子字符串
在这个问题中，我们需要将括号字符串拆分为有效的组。当所有左括号都有相关的右括号时，我们可以说括号组是有效的。
问题陈述
我们得到一个包含左括号和右括号的字符串。我们需要拆分字符串以获得最大有效的括号字符串。
示例
Input: par = "(())()(()())" Output: (()), (), (()()),
解释
每个子字符串包含有效的括号序列。
Input: par = "()()" Output: (), ()
解释
我们将字符串拆分为两个组。
Input: par = "()(())" Output: (), (())
方法 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 <stdio.h>
#include <stdlib.h>
#include <string.h>
// Function to get balanced groups
char** getBalancedGroups(char* par) {
char** ans = NULL;
int open = 0;
int close = 0;
char* temp = NULL;
int len = strlen(par);
// To store the result
int ansSize = 0;
// Return NULL if the string is empty
if (len == 0)
return ans;
// Allocate memory for the result array
ans = (char**)malloc(sizeof(char*) * len);
// Initialize temporary string
temp = (char*)malloc(sizeof(char) * (len + 1));
temp[0] = '\0';
for (int p = 0; p < len; p++) {
// Append the current character to the temporary string
strncat(temp, &par[p], 1);
// 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[ansSize] = (char*)malloc(sizeof(char) * (p + 2));
strcpy(ans[ansSize], temp);
ansSize++;
temp[0] = '\0'; // Reset the temporary string
}
}
// Resize the result array
ans = (char**)realloc(ans, sizeof(char*) * ansSize);
ans[ansSize] = NULL;
free(temp); // Free the temporary string
return ans;
}
int main() {
char par[] = "(())()(()())";
char** balancedGroup = getBalancedGroups(par);
printf("The valid groups of parenthesis are - ");
for (int i = 0; balancedGroup[i] != NULL; i++) {
printf("%s, ", balancedGroup[i]);
free(balancedGroup[i]); // Free memory used by each valid group
}
free(balancedGroup); // Free memory used by the result array
return 0;
}
输出
The valid groups of parenthesis are - (()), (), (()()),
#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 - (()), (), (()()),
import java.util.ArrayList;
import java.util.List;
public class BalancedGroups {
public static List<String> getBalancedGroups(String par) {
List<String> ans = new ArrayList<>(); // Initialize the result list
int open = 0;
int close = 0;
StringBuilder temp = new StringBuilder();
int len = par.length(); // Calculate the length of the input string
if (len == 0) {
return ans;
}
for (int p = 0; p < len; p++) {
temp.append(par.charAt(p)); // Append the current character to the temporary string
if (par.charAt(p) == '(') {
open++; // Increment the open bracket count
} else if (par.charAt(p) == ')') {
close++; // Increment the close bracket count
}
if (open == close) { // If the counts are equal, it's a valid group
ans.add(temp.toString()); // Add the temporary string to the result list
temp.setLength(0); // Reset the temporary string
}
}
return ans;
}
public static void main(String[] args) {
String par = "(())()(()())";
List<String> balancedGroup = getBalancedGroups(par); // Get balanced groups
System.out.print("The valid groups of parenthesis are - ");
for (String group : balancedGroup) {
System.out.print(group + ", ");
}
}
}
输出
The valid groups of parenthesis are - (()), (), (()()),
def getBalancedGroups(par):
ans = [] # Initialize the result list
open = 0
close = 0
temp = ""
len_par = len(par) # Calculate the length of the input string
if len_par == 0:
return ans
for p in range(len_par):
temp += par[p] # Append the current character to the temporary string
if par[p] == '(':
open += 1 # Increment the open bracket count
elif par[p] == ')':
close += 1
if open == close: # If the counts are equal, it's a valid group
ans.append(temp) # Add the temporary string to the result list
temp = ""
return ans
if __name__ == "__main__":
par = "(())()(()())"
balancedGroup = getBalancedGroups(par) # Get balanced groups
print("The valid groups of parenthesis are -", ", ".join(balancedGroup)) # Print the valid groups
输出
The valid groups of parenthesis are - (()), (), (()()),
时间复杂度 − O(N) 用于遍历字符串。
空间复杂度 − O(N) 用于存储有效子序列。
在这个问题中，我们学习了如何找到括号的有效序列。我们使用这样的逻辑：当每个左括号都有一个相关的右括号时，我们可以说它是一个有效的子序列并拆分字符串。
更新于: 2023年10月27日
108 次查看
广告