Problem
Given a string pattern of 0s, 1s, and ?s (wildcards), generate all 0-1 strings that match this pattern.
e.g. 1?00?101 -> [10000101, 10001101, 11000101, 11001101].
You can generate the strings in any order that suits you.
Solution
/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : Generate strings with pattern
permutations of the strings in the array
Created Date : 26-06-2013
Last Modified :
============================================================================
*/
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <string>
#include <vector>
#include <queue>
using namespace std;
void GenerateStringsWithPattern1(string& pattern, vector<string>& vec)
{
queue<string> q;
q.push(pattern);
while(!q.empty()){
string str = q.front();
q.pop();
int idx = str.find('?');
if(idx != string::npos){
str[idx] = '0';
q.push(str);
str[idx] = '1';
q.push(str);
}
else{
vec.push_back(str);
}
}
}
int main(int argc, char* argv[])
{
vector<string> testCases;
testCases.push_back("1?00?101");
testCases.push_back("1??0?101");
testCases.push_back("?");
testCases.push_back("??");
testCases.push_back("???");
testCases.push_back("1");
testCases.push_back("101");
for(int i = 0; i < testCases.size(); ++i){
vector<string> output;
cout << "---------------------------" << endl;
cout << "The pattern is " << testCases[i] << endl;
GenerateStringsWithPattern1(testCases[i], output);
copy(output.begin(), output.end(), ostream_iterator<string>(cout, " "));
cout << endl;
}
return 0;
}
Output
---------------------------
The pattern is 1?00?101
10000101 10001101 11000101 11001101
---------------------------
The pattern is 1??0?101
10000101 10001101 10100101 10101101 11000101 11001101 11100101 11101101
---------------------------
The pattern is ?
0 1
---------------------------
The pattern is ??
00 01 10 11
---------------------------
The pattern is ???
000 001 010 011 100 101 110 111
---------------------------
The pattern is 1
1
---------------------------
The pattern is 101
101
Press any key to continue . . .