平衡括号意味着如果我们有一串括号，那么每个开括号都有一个对应的闭括号，并且括号对是正确嵌套的。字符串的大小应该是偶数。在这个问题中，我们给出了一个包含字符’?’的括号字符串，我们的任务是通过将’?’替换为适当的括号来形成每个可能的平衡括号字符串。在我们给定的字符串中，只使用圆括号'(‘和’)’。
示例示例
Input 1: str = “()(?)?”Output 1: ()(())
Explanation
的中文翻译为：
解释
只有一个平衡的字符串可以通过替换’?’来形成。
Input 2: str = “??????”
Output 2: ((()))(()())(())()()(())()()()
Explanation
的中文翻译为：
解释
有两种可能的方法来形成一个平衡的字符串。
一种方法是用一个开括号替换索引0、1和2，用一个闭括号替换其他索引。
第二种方法是用一个开括号替换索引0、1和3，并用一个闭括号替换其他索引。
第三种方法是用开括号替换索引0、1和4，用闭括号替换其他索引。
第四种方法是用一个开括号替换索引为0、2和3的位置，用一个闭括号替换其他索引的位置。
最后一种方法是用开括号替换索引0、2和4，用闭括号替换其他索引。
方法
我们已经看到了上面给定字符串的示例，让我们继续下一步的方法-
我们可以使用回溯法来解决这个问题。
让我们在下面讨论这种方法 –
首先，我们将初始化一个名为’create’的函数，用于在将’?’替换为括号后创建所有可能的字符串，参数为str和index = 0。
在这个函数中，
−> 首先，我们设置了基本条件。如果我们到达了字符串的结束点，那么我们必须将该字符串传递给“check”函数来验证字符串是否平衡。如果它是平衡的，则打印该字符串。
−>如果字符串的当前字符是‘?’，
首先，将其替换为开括号，并调用相同的函数来检查是否到达字符串的末尾。
其次，用闭括号替换它，并再次调用相同的函数来检查我们是否已经到达字符串的末尾。
最后，我们回溯字符串并将当前字符赋值为‘?’
−> 否则，如果字符串的当前字符是括号，则通过调用相同的函数移动到下一个索引。
初始化’check’函数以验证字符串是否平衡。
−> 在这个函数中，我们初始化堆栈，然后进行检查
−> 如果字符串的第一个字符是闭括号，则返回false
−> 如果当前括号已关闭，则有两种情况：如果栈为空，则返回false，因为没有对应的开括号。否则，从栈中弹出对应的开括号。
−> 最后，我们检查堆栈是否为空，如果为空则表示字符串是平衡的，返回true，否则还有一些括号剩余，表示字符串不平衡，返回false。
Example
的中文翻译为：
示例
下面是用于上述回溯方法获取所有平衡字符串的C++代码
#include using namespace std; // Function 'check' to verify whether the string is balanced or notbool check(string str){ stack S; // created stack // If the first character of the string is a close bracket, then return false if (str[0] == ')') { return false; } // Traverse the string using for loop for (int i = 0; i < str.size(); i++) { // If the current character is an open bracket, then push it into the stack if (str[i] == '(') { S.push('('); } // If the current character is a close bracket else { // If the stack is empty, there is no corresponding open bracket return false if (S.empty()){ return false; } // Else pop the corresponding opening bracket from the stack else S.pop(); } } // If the stack is empty, return true if (S.empty()){ return true; } else { return false; }} // Function 'create' to create all possible bracket stringsvoid create(string str, int i){ // If reached the end of the string if (i == str.size()) { // passed 'str' to the 'check' function to verify whether the string is balanced or not if (check(str)) { // If it is a balanced string cout<< str << endl; // print the string } return; } // If the current character of the string is '?' if (str[i] == '?') { str[i] = '('; // replace ? with ( create(str, i + 1); // continue to next character str[i] = ')'; // replace ? with ) create(str, i + 1); // continue to next character // backtrack str[i] = '?'; } // If the current character is bracketed then move to the next index else { create(str, i + 1); }} int main(){ string str = "??????"; //given string // Call the function create (str, 0); return 0;}
输出
((()))(()())(())()()(())()()()
时间复杂度和空间复杂度
上述代码的时间复杂度为O(N*(2^N))，因为我们需要在字符串上进行回溯。
上述代码的空间复杂度为O(N)，因为我们将括号存储在堆栈中。
其中N是字符串的大小。
结论
在本教程中，我们实现了一个程序，用于打印所有平衡的括号字符串，可以通过替换通配符‘?’来形成。我们实现了一种回溯的方法。时间复杂度为O(N*(2^N)，空间复杂度为O(N)。其中N是字符串的大小。
以上就是打印所有通过替换通配符“？”而形成的平衡括号字符串的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1444655.html
微信扫一扫 
支付宝扫一扫 
