資料結構
網路
關係型資料庫管理系統 (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 次檢視
廣告