打印所有通过替换通配符'？”而形成的平衡括号字符串

平衡括号意味着如果我们有一串括号，那么每个开括号都有一个对应的闭括号，并且括号对是正确嵌套的。字符串的大小应该是偶数。在这个问题中，我们给出了一个包含字符'?'的括号字符串，我们的任务是通过将'?'替换为适当的括号来形成每个可能的平衡括号字符串。在我们给定的字符串中，只使用圆括号'('和')'。

示例示例

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 <bits/stdc++.h>
using namespace std; 
// Function 'check' to verify whether the string is balanced or not
bool check(string str){
   stack<char> 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 strings
void 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是字符串的大小。

以上是打印所有通过替换通配符'？”而形成的平衡括号字符串的详细内容。更多信息请关注PHP中文网其他相关文章！