Write program to replace every ‘#’ symbol with a binary number 0 and 1 and generate all possible combination
Examples :
Input : 11#1 Output : 1101 1111 Input : 1#1# Output : 1010 1011 1110 1111
Approach :
In this problem we are first going to store the index of all the '#' in string,in the vector idx, and also there count in length l. Then we are going to initialize a string as all 0s and of length l as bin. after that we are going to replace the '#' with bin,and after replacing print the string and find next binary number and looping it for 2^l to get all permutations(2^l). Also BinNext is used to find next binary number as a string,
Implementation :
//C++ program to replace every '#' symbol with a binary number 0 and 1 and generate all possible combination
#include<bits/stdc++.h>
using namespace std;
//Function to find next binary number as a string
string BinNext(string num)
{
int i,l = num.size();
// examine bits from the right
for (i=l-1; i>=0; i--)
{
// if '0' is encountered, convert
// it to '1' and then break
if (num.at(i) == '0')
{
num.at(i) = '1';
break;
}
// otherwise convert '1' to '0'
else
num.at(i) = '0';
}
// final binary representation
// of the required integer
return num;
}
//Generate possible strings function
void printCOMB(string s)
{
int sz = s.length(),length = 0;//sz to store size of string
vector< int > idx; //vector idx to store index of '#'' in code
for(int i = 0; i < sz; i++)
{
if(s[i] =='#')
idx.push_back(i) , length++;//pushing the index of '#'
}
//bin is going to store current binary string that
//is going to replace the '#'
string bin(length,'0'); //initializing the string with all zeros of length
//loop for all permutation in sorted order over 2^length
for(int j = 1;j <= (1<<length);j++)
{ //loop for replacing the '#' with bin
for(int i = 0;i < length;i++)
s[idx[i]]=bin[i];
cout<<s<<" ";
//incrementing the bin as a binary string
//example 100-->101,010-->011
bin=BinNext(bin);
}
}
//Driver function
int main()
{
string s = "1#1#";
printCOMB(s);
}
Output :
1010 1011 1110 1111
Time Complexity : O(2^n) Space complexity : O(n)