Dada una string que contiene ‘0’, ‘1’ y ‘?’ caracteres comodín, genere todas las strings binarias que se pueden formar reemplazando cada carácter comodín por ‘0’ o ‘1’.
Ejemplo :
Input str = "1??0?101"
Output:
10000101
10001101
10100101
10101101
11000101
11001101
11100101
11101101
Método 1 (usando la recursividad)
Pasamos el índice del siguiente carácter a la función recursiva. Si el carácter actual es un carácter comodín ‘?’, lo reemplazamos con ‘0’ o ‘1’ y hacemos lo mismo con todos los caracteres restantes. Imprimimos la string si llegamos a su final.
A continuación se muestra la implementación recursiva.
Algoritmo:
Paso 1: Primero inicialice la string con algunos caracteres comodín.
Paso 2: compruebe si la posición del índice es igual al tamaño de la string, si es de retorno.
Paso 3: si el carácter comodín está presente en la ubicación del índice, reemplácelo por 0 o 1 según corresponda.
Paso 4: Imprima la salida
C++
// Recursive C++ program to generate all binary strings
// formed by replacing each wildcard character by 0 or 1
#include <iostream>
using namespace std;
// Recursive function to generate all binary strings
// formed by replacing each wildcard character by 0 or 1
void print(string str, int index)
{
if (index == str.size())
{
cout << str << endl;
return;
}
if (str[index] == '?')
{
// replace '?' by '0' and recurse
str[index] = '0';
print(str, index + 1);
// replace '?' by '1' and recurse
str[index] = '1';
print(str, index + 1);
// No need to backtrack as string is passed
// by value to the function
}
else
print(str, index + 1);
}
// Driver code to test above function
int main()
{
string str = "1??0?101";
print(str, 0);
return 0;
}
Java
// Recursive Java program to generate all
// binary strings formed by replacing
// each wildcard character by 0 or 1
import java.util.*;
import java.lang.*;
import java.io.*;
class binStr
{
// Recursive function to generate all binary
// strings formed by replacing each wildcard
// character by 0 or 1
public static void print(char str[], int index)
{
if (index == str.length)
{
System.out.println(str);
return;
}
if (str[index] == '?')
{
// replace '?' by '0' and recurse
str[index] = '0';
print(str, index + 1);
// replace '?' by '1' and recurse
str[index] = '1';
print(str, index + 1);
// NOTE: Need to backtrack as string
// is passed by reference to the
// function
str[index] = '?';
}
else
print(str, index + 1);
}
// driver code
public static void main (String[] args)
{
String input = "1??0?101";
char[] str = input.toCharArray();
print(str, 0);
}
}
// This code is contributed by Chhavi
Python3
# Recursive Python program to generate all
# binary strings formed by replacing
# each wildcard character by 0 or 1
# Recursive function to generate all binary
# strings formed by replacing each wildcard
# character by 0 or 1
def _print(string, index):
if index == len(string):
print(''.join(string))
return
if string[index] == "?":
# replace '?' by '0' and recurse
string[index] = '0'
_print(string, index + 1)
# replace '?' by '1' and recurse
string[index] = '1'
_print(string, index + 1)
# NOTE: Need to backtrack as string
# is passed by reference to the
# function
string[index] = '?'
else:
_print(string, index + 1)
# Driver code
if __name__ == "__main__":
string = "1??0?101"
string = list(string)
_print(string, 0)
# This code is contributed by
# sanjeev2552
# Note: function name _print is used because
# print is already a predefined function in Python
C#
// Recursive C# program to generate all
// binary strings formed by replacing
// each wildcard character by 0 or 1
using System;
class GFG
{
// Recursive function to generate
// all binary strings formed by
// replacing each wildcard character
// by 0 or 1
public static void print(char []str,
int index)
{
if (index == str.Length)
{
Console.WriteLine(str);
return;
}
if (str[index] == '?')
{
// replace '?' by
// '0' and recurse
str[index] = '0';
print(str, index + 1);
// replace '?' by
// '1' and recurse
str[index] = '1';
print(str, index + 1);
// NOTE: Need to backtrack
// as string is passed by
// reference to the function
str[index] = '?';
}
else
print(str, index + 1);
}
// Driver Code
public static void Main ()
{
string input = "1??0?101";
char []str = input.ToCharArray();
print(str, 0);
}
}
// This code is contributed by nitin mittal.
PHP
<?php
// Recursive PHP program to generate all binary strings
// formed by replacing each wildcard character by 0 or 1
// Recursive function to generate all binary strings
// formed by replacing each wildcard character by 0 or 1
function print1($str, $index)
{
if ($index == strlen($str))
{
echo $str."\n";
return;
}
if ($str[$index] == '?')
{
// replace '?' by '0' and recurse
$str[$index] = '0';
print1($str, $index + 1);
// replace '?' by '1' and recurse
$str[$index] = '1';
print1($str, $index + 1);
// No need to backtrack as string is passed
// by value to the function
}
else
print1($str, $index + 1);
}
// Driver code
$str = "1??0?101";
print1($str, 0);
// This code is contributed by chandan_jnu
?>
Javascript
<script>
// Recursive JavaScript program to generate all
// binary strings formed by replacing
// each wildcard character by 0 or 1
// Recursive function to generate
// all binary strings formed by
// replacing each wildcard character
// by 0 or 1
function print(str, index) {
if (index === str.length) {
document.write(str.join("") + "<br>");
return;
}
if (str[index] === "?") {
// replace '?' by
// '0' and recurse
str[index] = "0";
print(str, index + 1);
// replace '?' by
// '1' and recurse
str[index] = "1";
print(str, index + 1);
// NOTE: Need to backtrack
// as string is passed by
// reference to the function
str[index] = "?";
} else print(str, index + 1);
}
// Driver Code
var input = "1??0?101";
var str = input.split("");
print(str, 0);
</script>
Producción:
10000101 10001101 10100101 10101101 11000101 11001101 11100101 11101101
Complejidad de tiempo: O (1), ya que cambia directamente el carácter en el carácter comodín, la complejidad será O (1).
Método 2 (usando la cola)
También podemos lograr esto usando la iteración. La idea es usar la cola. Encontramos la posición de la primera aparición del carácter comodín en la string de entrada y la reemplazamos por ‘0’, luego ‘1’ y empujamos ambas strings a la cola. Luego sacamos la siguiente string de la cola y repetimos el proceso hasta que la cola esté vacía. Si no quedan caracteres comodín, simplemente imprimimos la string.
Implementación iterativa de C++ usando la cola.
C++
// Iterative C++ program to generate all binary
// strings formed by replacing each wildcard
// character by 0 or 1
#include <iostream>
#include <queue>
using namespace std;
// Iterative function to generate all binary strings
// formed by replacing each wildcard character by 0
// or 1
void print(string str)
{
queue<string> q;
q.push(str);
while (!q.empty())
{
string str = q.front();
// find position of first occurrence of wildcard
size_t index = str.find('?');
// If no matches were found,
// find returns string::npos
if(index != string::npos)
{
// replace '?' by '0' and push string into queue
str[index] = '0';
q.push(str);
// replace '?' by '1' and push string into queue
str[index] = '1';
q.push(str);
}
else
// If no wildcard characters are left,
// print the string.
cout << str << endl;
q.pop();
}
}
// Driver code to test above function
int main()
{
string str = "1??0?101";
print(str);
return 0;
}
Java
/*package whatever //do not write package name here */
import java.io.*;
import java.util.*;
class GFG {
// Iterative Java program to generate all binary
// strings formed by replacing each wildcard
// character by 0 or 1
// Iterative function to generate all binary strings
// formed by replacing each wildcard character by 0
// or 1
static void print(String str)
{
Queue<String> q = new LinkedList<>();
q.add(str);
while (!q.isEmpty())
{
str = q.remove();
// find position of first occurrence of wildcard
int index = str.indexOf('?');
// If no matches were found,
// find returns string::npos
if(index != -1)
{
// replace '?' by '0' and add string into queue
str = str.substring(0,index) + '0' + str.substring(index+1);
q.add(str);
// replace '?' by '1' and add string into queue
str = str.substring(0,index) + '1' + str.substring(index+1);
q.add(str);
}
else
// If no wildcard characters are left,
// print the string.
System.out.println(str);
}
}
// Driver Code
public static void main(String args[])
{
String str = "1??0?101";
print(str);
}
}
// This code is contributed by shinjanpatra
Python3
# Iterative Python program to generate all binary
# strings formed by replacing each wildcard
# character by 0 or 1
# Iterative function to generate all binary strings
# formed by replacing each wildcard character by 0
# or 1
def Print(Str):
q = []
q.append(Str)
while(len(q) > 0):
Str = q[0]
# find position of first occurrence of wildcard
try:
index = Str.index('?')
except ValueError:
index = -1
# If no matches were found,
# find returns -1
if(index != -1):
# replace '?' by '0' and push string into queue
s1=Str.replace('?','0',1)
q.append(s1)
# replace '?' by '1' and push string into queue
s2=Str.replace('?','1',1)
q.append(s2)
else:
# If no wildcard characters are left,
# print the string.
print(Str)
q.pop(0)
# Driver code
Str = "1??0?101"
Print(Str)
# This code is contributed by Pushpesh Raj
C#
// C# program to implement the approach
using System;
using System.Collections.Generic;
public class GFG
{
// Iterative C# program to generate all binary
// strings formed by replacing each wildcard
// character by 0 or 1
// Iterative function to generate all binary strings
// formed by replacing each wildcard character by 0
// or 1
static void print(string Str)
{
var q = new List<string>();
q.Add(Str);
while (q.Count > 0) {
Str = q[0];
// find position of first occurrence of wildcard
int index = Str.IndexOf('?');
// If no matches were found,
// find returns -1
if (index != -1) {
// replace '?' by '0' and push string into
// queue
Str = Str.Substring(0, index) + '0'
+ Str.Substring(index + 1);
q.Add(Str);
// replace '?' by '1' and push string into
// queue
Str = Str.Substring(0, index) + '1'
+ Str.Substring(index + 1);
q.Add(Str);
}
else {
// If no wildcard characters are left,
// print the string.
Console.WriteLine(Str);
}
q.RemoveAt(0);
}
}
// Driver Code
public static void Main(string[] args)
{
string str = "1??0?101";
// Function call
print(str);
}
}
// This code is contributed by phasing17
Javascript
<script>
// Iterative JavaScript program to generate all binary
// strings formed by replacing each wildcard
// character by 0 or 1
// Iterative function to generate all binary strings
// formed by replacing each wildcard character by 0
// or 1
function Print(Str){
let q = []
q.push(Str)
while (q.length > 0){
let Str = q[0]
// find position of first occurrence of wildcard
let index = Str.indexOf('?')
// If no matches were found,
// find returns -1
if(index != -1)
{
// replace '?' by '0' and push string into queue
Str = Str.replace(Str[index] , '0')
q.push(Str)
// replace '?' by '1' and push string into queue
Str = Str.replace(Str[index] , '1')
q.push(Str)
}
else
{
// If no wildcard characters are left,
// print the string.
document.write(Str,"</br>")
}
q.shift()
}
}
// Driver code to test above function
let Str = "1??0?101"
Print(Str)
// This code is contributed by shinjanpatra
</script>
Producción:
10000101 10001101 10100101 10101101 11000101 11001101 11100101 11101101
Complejidad de tiempo: O(n), donde n es el tamaño de una string.
Espacio Auxiliar: O(1)
Método 3 (usando str y recursividad)
C++
// C++ prgoram to implement the approach
#include <bits/stdc++.h>
using namespace std;
/* we store processed strings in all (array)
we see if string as "?", if so, replace it with 0 and 1
and send it back to recursive func until base case is
reached which is no wildcard left */
vector<string> res;
void genBin(string s)
{
auto pos = s.find('?');
if (pos != string::npos) {
// copying s to s1
string s1 = s;
// replacing first occurrence of ?
// with 0
s1.replace(pos, 1, "0");
// copying s to s2
string s2 = s;
// replacing first occurrence of ?
// with 1
s2.replace(pos, 1, "1");
genBin(s1);
genBin(s2);
}
else {
res.push_back(s);
}
}
// Driver code
int main()
{
genBin("1??0?101");
for (string x : res) {
cout << x << " ";
}
}
// This code is contributed by phasing17
Java
import java.io.*;
import java.util.*;
class GFG
{
// we store processed strings in all (array)
// we see if string as "?", if so, replace it with 0 and 1
// and send it back to recursive func until base case is reached
// which is no wildcard left
static ArrayList<String>res = new ArrayList<String>();
static void genBin(String s) {
if (s.indexOf('?') != -1) {
String s1 = s.replaceFirst("\\?", "0"); // only replace once
String s2 = s.replaceFirst("\\?", "1"); // only replace once
genBin(s1);
genBin(s2);
}
else res.add(s);
}
public static void main(String[] args) {
genBin("1??0?101");
System.out.println(res);
}
}
Python3
#we store processed strings in all (array)
#we see if string as "?", if so, replace it with 0 and 1
#and send it back to recursive func until base case is reached
#which is no wildcard left
res = []
def genBin(s):
if '?' in s:
s1 = s.replace('?','0',1) #only replace once
s2 = s.replace('?','1',1) #only replace once
genBin(s1)
genBin(s2)
else: res.append(s)
# Driver code
genBin("1??0?101")
print(res)
# This code is contributed by
# divay pandey
C#
// C# code to implement the approach
using System;
using System.Collections.Generic;
class GFG {
// we store processed strings in all (array)
// we see if string as "?", if so, replace it with 0 and
// 1 and send it back to recursive func until base case
// is reached which is no wildcard left
static List<string> res = new List<string>();
static void genBin(string s)
{
int ind = s.IndexOf("?");
if (ind != -1) {
string s1 = s.Remove(ind, 1).Insert(
ind, "0"); // only replace once
string s2 = s.Remove(ind, 1).Insert(
ind, "1"); // only replace once
genBin(s1);
genBin(s2);
}
else
res.Add(s);
}
// Driver code
public static void Main(string[] args)
{
genBin("1??0?101");
foreach(var ele in res) Console.Write(ele + " ");
}
}
// This code is contributed by phasing17
Javascript
<script>
/* we store processed strings in all (array)
we see if string as "?", if so, replace it with 0 and 1
and send it back to recursive func until base case is reached
which is no wildcard left */
let res = []
function genBin(s){
if(s.includes('?')){
let s1 = s.replace(/\?/,'0') //only replace once
let s2 = s.replace(/\?/,'1') //only replace once
genBin(s1)
genBin(s2)
}else{
res.push(s)
}
}
// Driver code
genBin("1??0?101")
document.write(res)
// This code is contributed by
// Santanu Panda
</script>
Producción:
['10000101', '10001101', '10100101', '10101101', '11000101', '11001101', '11100101', '11101101']
Complejidad de tiempo: O(1)
Espacio Auxiliar: O(1)
Este artículo es una contribución de Aditya Goel . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA