CareerCup

non recursive algorithm is provided on sites.google.com/site/spaceofjameschen/home/string/generate-strings-with-a-specified-pattern----google

use simple recursion..call function print(string name,0)

void print(char a[],int i)
{
if(a[i]=='\0')
{
printf("%s\n");
}
if(a[i]=='?')
{
a[i]='0';
print(a,i+1);
a[i]='1';
print(a,i+1);
}
else print(a,i+1);
}

Recursion. Not much to elaborate on.

static LinkedList<String> generate(String pattern) {
	LinkedList<String> strings = new LinkedList<String>();
	int pos = pattern.indexOf("?");
	if(pos < 0) {
		strings.add(pattern);
	} else {
		String zeroPattern = pattern.substring(0, pos) + "0" + pattern.substring(pos+1);
		String onePattern = pattern.substring(0, pos) + "1" + pattern.substring(pos+1);
		strings.addAll(generate(zeroPattern));
		strings.addAll(generate(onePattern));
	}
	return strings;
}

there is a fault in the question if m nt wrong....this is obviously they asked things related to the compiler design/theory of computing related topics....or shud i say turing machine related things...but the problem is on what basis Google wants u to print those 1's or 00's ,cause ofcourse u need to generate 101 only once...but what about the first two elements...upto infinity ??

public static void outputAllString(String pattern){
		ArrayList<String> potential_pattern=new ArrayList<String>();
		potential_pattern.add("");
		for(int i=0; i<pattern.length(); i++){
			for(int j=potential_pattern.size()-1; j>=0; j--){
				String s=potential_pattern.remove(j);
				if(pattern.charAt(i)!='?'){
					s+=pattern.charAt(i);
					potential_pattern.add(j, s);
				}
				else{
					String temp=s+"0";
					potential_pattern.add(j,temp);
					temp=s+"1";
					potential_pattern.add(j, temp);
				}
			}
		}
		//output result
		for(String s:potential_pattern)
			System.out.println(s);
	}

It can be done by rotating the substring whose length is equal to the number of the wildcards and is initialized to zero. Use every rotation to fill the wildcards locations within the original string with the current values of the substring. Here's the code to compute the substrings, iteratively. The rest if trivial:

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<string.h>

void swap(char *s, int i)
{
 char tmp=s[i];
 s[i]=s[i-1];
 s[i-1]=tmp;
}

int main()
{
  char *s="000";
  int i,j,cnt=0;
  int n=strlen(s);
  clrscr();
  puts(s);
  puts("\n");
  while(cnt!=n)
  {
   s[cnt]=s[cnt]-'0'+1+'0';
   puts(s);
   puts("\n");
   if(cnt!=n-1)
   {
    for(i=1;i<n;i++)
     {
      swap(s,i);
      puts(s);
      puts("\n");
     }
   }
   cnt++;
  }
  getch();
  return 1;
}

I did the problem in Notepad, so as to not benefit from autocomplete. Then I fixed the few errors I had (i.e. I had written StringBuffer.add() instead of StringBuffer.append()) and verified that it works correctly. Here is my answer. I would appreciate any critique.

import java.util.List;
import java.util.ArrayList;

public class PatternMatcher {
    public static void main(String[] args) {
        List<String> matches = PatternMatcher.generateAllMatches(args[0]);
        for (String match : matches) {
            System.out.println(match);
        }
    }

    public static List<String> generateAllMatches(String pattern) {
        List<String> matches = new ArrayList<String>();
        if (null == pattern || 0 == pattern.length()) {
            return matches;
        }

        String[] subPatterns = pattern.split("\\?");
        if (1 == subPatterns.length) {
            // pattern included zero ?s
            matches.add(subPatterns[0]);
            return matches;
        }

        int permutations = (int)(Math.pow(2, subPatterns.length-1));
        for (int i=0; i<permutations; ++i) {
            matches.add(generateSubPattern(i, subPatterns));
        }
        return matches;
    }

    private static String generateSubPattern(int valsToInsert, String[] subPatterns) {
        StringBuffer buf = new StringBuffer(subPatterns[0]);
        for (int i=0; i<subPatterns.length-1; ) {
            String val = Integer.toString((valsToInsert & (1<<i)) >> i);
            buf.append(val); // Adds the bits of i from right to left
            buf.append(subPatterns[++i]);
        }
        return buf.toString();
    }
}

public static void generateResultSet(String inp)
{
if (inp == null || inp.length() == 0)
return;
if (!inp.contains("?"))
{
System.out.println(inp);
return;
}
else
{
String withZero = inp.replaceFirst("\\?", "0");
String withOne = inp.replaceFirst("\\?", "1");
generateResultSet(withZero);
generateResultSet(withOne);

}
}

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Stack;

public class WildCardReplacer {
    private Substitutor substritutor;

    public WildCardReplacer() {
        substritutor = new Substitutor();
    }

    public List<String> substituteWildChar(String strWithWildChar, String wildChar) {
        Stack<String> stack = new Stack<String>();
        stack.push(strWithWildChar);
        String[] substitutedStr = null;
        String strContainsWildChar = null;
        List<String> stringlistRelacedWildCharList = new ArrayList<String>();
        while (!stack.isEmpty()) {
            strContainsWildChar = stack.pop();
            if (strContainsWildChar.indexOf(wildChar) >= 0) {
                substitutedStr = substritutor.substitute(strContainsWildChar, wildChar);
                for (String sub : substitutedStr) {
                    stack.push(sub);
                }
            } else {
                stringlistRelacedWildCharList.add(strContainsWildChar);
            }
        }
        return stringlistRelacedWildCharList;
    }

    public static void main(String[] args) {
        System.out.println(new WildCardReplacer().substituteWildChar("?001?00?", "?"));
    }

}

class Substitutor {
    private static Map<String, String[]> substituteStringMap = new HashMap<String, String[]>();
    static {
        String[] substituteChar = { "0", "1" };
        substituteStringMap.put("?", substituteChar);
    }

    public String[] substitute(String srcStr, String wildChar) {
        if (substituteStringMap.containsKey(wildChar)) {
            String[] substituteChar = substituteStringMap.get(wildChar);
            String[] substitutedStr = new String[substituteChar.length];
            int indx = 0;
            for (String schar : substituteChar) {
                substitutedStr[indx++] = srcStr.replaceFirst("\\" + wildChar, schar);
            }
            return substitutedStr;
        }
        throw new RuntimeException(" Wild char :" + wildChar + " not supported!!");
    }
}

We can tweak the idea we use to generate truth table to support this.

Logic:

-get the no. of '?' char in string given [ noOfWildChar ] 

-now calculate no of possible strings = [ noOfStrings = 2 ^ noOfWildChar ]

-write a loop initiating from 0 to noOfStrings having index as loopIndex

-Inside Loop:
	--calculate binary form of loopIndex for ex: 11 = 1011, 12 = 1100, 17 = 10001 [binaryForm]
	--now start replacing '?' char with binaryForm sequence and print it.

For Ex:
String = 1 1 0 ? 1 ? 0 0 ? ? 1 ?
noOfWildChar = 5
noOfStrings = (2^5) = 32

Loop
	-loopIndex = 0 then binaryForm = 00000 hence put '0' at all occurance of '?' char 
	-loopIndex = 1 .........
	-loopIndex = 2 .........
	-...
	-..
	-loopIndex = 11 then binaryForm = 01011 hence put '0' at first and third occurance of '?' and rest fill '1' 
	-..
	-..
	-loopIndex = 31 then binaryForm = 11111 hence put '1' at all occurance of '?' char 	
END LOOP

{{
//i can think of the solution which is of the O(n.2^k) where n is the length of the string and k is the count of '?' in the string... as there would 2^k patterns for k '?' and we need to write all..

Is there any better solution???
}}

#include<iostream>
#include<string.h>
using namespace std;

void GenarateString ( string s_pattern , int index ){
int i_size=s_pattern.size();
if( index == i_size ){
std::cout<<s_pattern<<std::endl;
return;
}
if( s_pattern[index]== '?' ){
s_pattern[index]='0';
GenarateString ( s_pattern , index + 1 );
s_pattern[index]='1';
GenarateString ( s_pattern , index + 1 );
}
else
GenarateString ( s_pattern , index + 1 );
}


int main(){
int i_num;
std::cin>>i_num;
string s_pattern;
for( int i=0 ; i<i_num ; i++ ){
std::cin>>s_pattern;
std::cout<<"The pattern is= "<<s_pattern<<std::endl;
GenarateString(s_pattern , 0 );
}
}

Let it be a binary number. ? ? ? can be of range 000 to 111 which is decimal 0 to 7. plug the result into ?s.

A non-recursive solution is here:

public static void WildCardPrint(string wildcard)
        {
            int count = 0;
            foreach (char c in wildcard)
            {
                if (c == '?')
                {
                    count++;
                }
            }

            int permutation = (int)Math.Pow(2, count);
            for (int perm = 0; perm < permutation; perm++)
            {    
                int current = perm;
                int qmarkSoFar = 0;
                for (int index = 0; index < wildcard.Length; index++)
                {   
                    if (wildcard[index] != '?')
                    {
                        Console.Write(wildcard[index]);
                    }
                    else
                    {
                        qmarkSoFar++;
                        int digit = count-qmarkSoFar;
                        if (current < Math.Pow(2, digit))
                        {
                            Console.Write('0');

                        }
                        else
                        {
                            Console.Write('1');
                            current -= (int)Math.Pow(2, digit);
                        }
                    }
                }

                Console.WriteLine();
            }
        }

if ARGV.size == 1
strng = ARGV[0]
else
strng = "10?01?11"
end
input=0
itter=0
puts strng.size
strng.split(//).each{|chr| input+=1 if (chr == '?')}
outerloop = 2**input
innerloop = input
cont = Array.new
var = Array.new
itter = 0
def show_array(input, var, strng)
itter=0
while(itter < input)
strng = strng.sub('?',var[itter].to_s)
itter+=1
end
puts strng
end
while(itter < input)
cont[itter]=2**(input - 1 - itter)
var[itter]=0
itter+=1
end

itter=1
litter=0
while(itter <= outerloop)
show_array(input, var, strng)
while(litter < input )
if( itter%cont[litter] == 0 )
if(var[litter] == 0)
var[litter]=1
else
var[litter]=0
end
end
litter+=1
end
litter=0
itter+=1
end
[amitn@amitn-ux railprac]$ ruby pattern.rb "11?00?11?"
9
110000110
110000111
110001110
110001111
111000110
111000111
111001110
111001111

Wrote non recursive program in RUBY.

public static void theCode(String pattern) {
		System.out.println(pattern);
		int temp = 0;
		LinkedList<Integer> locations = new LinkedList<Integer>();

		for (int i = 0; i < pattern.length(); i++) {
			if (pattern.charAt(i) == '?') {
				temp++;
				locations.add(i);

			}
		}
		int limit = 1;
		for (int i = 1; i <= temp; i++)
			limit = limit * temp;

		System.out.println(limit);
		for (int i = 0; i < limit; i++) {
			String model=String.format("%" + temp + "s",Integer.toBinaryString(i)).replace(' ', '0');
			
			System.out.println(model);
			
			int q=0;
			for(int k=0; k<pattern.length();k++)
			{
				if(pattern.charAt(k)!='?' )
				{
					System.out.print(pattern.charAt(k));
				}
				else{
					System.out.print(model.charAt(q));
					q++;
				}
					
			}
			System.out.println();
			
			
			

		}

	}

static string[] generatePattern(string pattern)
        {
            int count = pattern.Count(c => c == '?');
            int comb = (int)Math.Pow(2, count);

            getPattern("0", 1);
            getPattern("1", 1);

            string[] generatedPatterns = new string[comb];
            for (int i = 0 ; i < patterns.Count; i++)
            {
                StringBuilder patternConvin = new StringBuilder(pattern);
                int index = -1;
                foreach (Char c in patterns[i])
                {
                    index = patternConvin.ToString().IndexOf('?', (index == -1) ? 0 : index);
                    patternConvin[index] = c;
                }
                generatedPatterns[i] = patternConvin.ToString();
            }
            return generatedPatterns;
        }

        static List<string> patterns = new List<string>();
        static string getPattern(string pchars, int c)
        {
            if (c < 3) c++;
            else return pchars;

            string zpat = getPattern(pchars + "0", c);
            if (!string.IsNullOrEmpty(zpat))
                patterns.Add(zpat);
            string opat = getPattern(pchars + "1", c);
            if (!string.IsNullOrEmpty(opat))
                patterns.Add(opat);

            return string.Empty;
        }

Java solution:

private static StringBuilder sb = new StringBuilder();
    public void genPattern(String str, int index){
        if(index == str.length()){
            System.out.println(sb.toString());
        }
        else if(str.charAt(index) == '?'){
            for(int i = 0; i < 2; i++){
                sb.append((char)(48+i));
                genPattern(str, index + 1);
                sb.deleteCharAt(sb.length() - 1);
            }            
        }
        else{
            sb.append(str.charAt(index));
            genPattern(str, index + 1);
            sb.deleteCharAt(sb.length() - 1);
        }
    }

Argument Can be any patteren with question mark "???" or ?10101?? or 0101010??

public  static void genrateStringFromPatteren(String strPattern){

        char[] charArray = strPattern.toCharArray();
        
        // No of Wild Card into String.
        int intNoWild = strPattern.length() - strPattern.replaceAll("\\?", "").length();
        
        // Power Function will run loop till possible unique combinations.
        for (int i = 0; i < Math.pow(2, intNoWild); i++) {
            
            // Get Binary for the number.
            String strCombination= this.getCombination(intNoWild, i);
            
            // This will get Value from Combination String to eplace in Array.
            int intCounter=0;
            
                for(int k=0; k<charArray.length; k++){
                    /* If array Location has Wildcard value then get combination
                        from the combination String and replace with this location.
                    */
                    if (charArray[k]=='?'){
                        charArray[k] = strCombination.charAt(intCounter);
                        /* This Counter Will keep track of the next value to be replaced.*/
                        intCounter++;
                    }        
                }    
                
                String output =new  String(charArray);
                System.out.println(output);
                
                // Reset Array to Populate the new combination.
                charArray = strPattern.toCharArray();
        }
        
    }
    
    public  static String getCombination(int valFormat, int NumberValue){
        String strCombination = Integer.toBinaryString(NumberValue);
        
        if ( strCombination.length()-1 < valFormat){
            for ( int i=strCombination.length(); i<valFormat; i++){
                    strCombination = "0" + strCombination;
            }
        }
        return strCombination;
    }

public class Solution{
  ArrayList<String> res;
  public ArrayList<String>Patten( String str ){
    res = new ArrayList<String>();  
    Patten_DP(str, new StringBuffer() , 0);
    return res;
  }
  private void Patten_DP(String str,StringBuffer buf , int index){
    if(index == str.length()) res.add(buf.toString());
    switch(str.charAt(index)){
      case '1':
        buf.add('1');
        break;
      case '0':
        buf.add('0');
        break;
      case '?':
        String buf2 = new StringBuffer(buf);
        buf.add('0');
        buf2.add('1');
        Patten_DP(str,buf , index+1);
        Patten_DP(str,buf2 , index+1);
        break;
    }
  }
}

Here's another approach:
1.Traverse the string and count the total number of wildcards that are included in the string.
2. Given n wildcards, it is clear that the total number of new strings that can be formed by filling these blank positions is n! (assuming that ? implies single character placement).
3. We can generate these n! permutations one-by-one and fill the wildcards.

I wrote a tail recursive version of the program. I ran the code. It works.
Here it is:

#include <iostream>
#include <cstdlib>

void print_wildcard(std::string str,std::string prefix)
{
	if(str[0]=='\0')
	{
		std::cout << prefix << "\n";
		return;
	}
	std::string from1 = "";
	from1 = str.substr(1);
	if(str[0]=='?')
	{
		print_wildcard("0"+from1,prefix);
		print_wildcard("1"+from1,prefix);
	}
	else
	{
		prefix += str[0];
		print_wildcard(from1,prefix);
	}
}

int main()
{
	std::string x = "1?00?101";
	print_wildcard(x,"");
        return(EXIT_SUCCESS);
}

#include <iostream>
#include <vector>

using namespace std;
vector<string> re;

string s;
vector<int> unknown;

void gen(int i, int n, string tmp)
{
if(i==n-1)
{
re.push_back(tmp);
return;
}
int j;

for(j=unknown[i]+1; j<unknown[i+1]; j++)
tmp[j]=s[j];
tmp[j]='0';
gen(i+1, n, tmp);
tmp[j]='1';
gen(i+1, n, tmp);
}

int main()
{
s="0101?01?0?";
unknown.push_back(-1);
string tmp;
tmp.resize(s.size());
for(int i=0; i<s.size(); i++)
{
if(s[i]=='?') unknown.push_back(i);
}
gen(0, unknown.size(), tmp);
for(auto e: re)
cout<<e<<endl;
return 0;
}

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		String input = "???";
		List<String> output = perm(input);
		for (String o : output) {
			System.out.println(o);
		}
	}
	
	private static List<String> perm(String input) {
		char[] chars = input.toCharArray();
		int totalWC = 0;
		for (char c : chars) {
			if (c == '?')
			totalWC++;
		}
		
		int totalPerms = (int)Math.pow(2, totalWC), position = 0;
		List<String> output = new ArrayList<>(totalPerms);
		
		StringBuilder sb = new StringBuilder();
		for (int i =0; i < totalPerms;i++) {
			sb = new StringBuilder();
			position = totalWC-1;
			for (int j =0;j < chars.length; j++) {
				char c = chars[j];
				if (c == '?') {
					sb.append(((i & (1<<position)) != 0) ? '1' : '0' );
					position--;
				} else {
					sb.append(c);
				}
			}
			output.add(sb.toString());
		}
		return output;
	}
}

def wildcards(orig):
    list_wildcard = list(orig)
    print orig
    if '?' in list_wildcard:
        indexes = [i for i, x in enumerate(list_wildcard) if x == '?']
        final = []
        for _ in indexes:
            for val in [0, 1]:
                temp = [val if x == '?' else x for x in list_wildcard]
                temp = ''.join(map(str, temp))
                final.append(int(temp))
        return final
    else:
        return ''.join(map(str, list_wildcard))


print wildcards('1?00?101')
print wildcards('101')

def wildcardzeroonecombo(strlist, currstr, currpos, strlen):
if currpos == strlen:
print currstr
return

c = strlist[currpos]
if c == '?':
for x in ('0','1'):
wildcardzeroonecombo(strlist, currstr + x, currpos + 1, strlen)
else:
wildcardzeroonecombo(strlist, currstr + c, currpos + 1, strlen)

if __name__== "__main__":
strzereone = '0?0?'
strlist = list(strzereone)
wildcardzeroonecombo(strlist, '', 0, len(strlist))

arr = "4646555?45656?564465?";
function A(arr){var k = arr.indexOf("?");
if(k != -1){
   	R = arr.slice(0,k);
	L = arr.slice(k+1,arr.length);
	let M = R +"0"+ L;
	let N = R +"1"+ L;


	if(M.indexOf("?") != -1) A(M);
	else console.log(M)
	if(N.indexOf("?") != -1) A(N);
	else console.log(N)
}
}
A(arr)

void maybeString(string input, int index, vector<string>& output) {

if (index >= input.length()) {
output.push_back(input);
return;
}

if(input[index] == '?') {
input[index] = '0';
maybeString(input, index + 1, output);

input[index] = '1';
maybeString(input, index + 1, output);

} else {
maybeString(input, index + 1, output);
}
}

void maybeString(string input, int index, vector<string>& output) {
    
    if (index >= input.length()) {
        output.push_back(input);
        return;
    }
    if(input[index] == '?') {
    input[index] = '0';
    maybeString(input, index + 1, output);
    
    input[index] = '1';
    maybeString(input, index + 1, output);

    } else {
        maybeString(input, index + 1, output);
    }
}

function getCombination(str, index=0, items=[]){
  if(str.indexOf('?') === -1) {
    items.push(str);
    return str;
  }
  if(str[index] === '?'){
    var L = str.slice(0, str.indexOf('?'));
    var R = str.slice(str.indexOf('?')+1, str.length);
    ++index
    getCombination(L+'0'+R, index, items);
    getCombination(L+'1'+R, index, items);
  } else {
    return getCombination(str, ++index, items);
  }
}
var items = [];
getCombination('1??0?101', 0, items);
console.log(items);

function getCombination(str, index=0, items=[]){
  if(str.indexOf('?') === -1) {
    items.push(str);
    return str;
  }
  if(str[index] === '?'){
    var L = str.slice(0, str.indexOf('?'));
    var R = str.slice(str.indexOf('?')+1, str.length);
    ++index
    getCombination(L+'0'+R, index, items);
    getCombination(L+'1'+R, index, items);
  } else {
    return getCombination(str, ++index, items);
  }
}
var items = [];
getCombination('1??0?101', 0, items);
console.log(items);

function getCombination(str, index=0, items=[]){
  if(str.indexOf('?') === -1) {
    items.push(str);
    return str;
  }
  if(str[index] === '?'){
    var L = str.slice(0, str.indexOf('?'));
    var R = str.slice(str.indexOf('?')+1, str.length);
    ++index
    getCombination(L+'0'+R, index, items);
    getCombination(L+'1'+R, index, items);
  } else {
    return getCombination(str, ++index, items);
  }
}
var items = [];
getCombination('1??0?101', 0, items);
console.log(items);

function getCombination(str, index=0, items=[]){
  if(str.indexOf('?') === -1) {
    items.push(str);
    return str;
  }
  if(str[index] === '?'){
    var L = str.slice(0, str.indexOf('?'));
    var R = str.slice(str.indexOf('?')+1, str.length);
    ++index
    getCombination(L+'0'+R, index, items);
    getCombination(L+'1'+R, index, items);
  } else {
    return getCombination(str, ++index, items);
  }
 }
 var items = [];
 getCombination('1??0?101', 0, items);
 console.log(items);

public void patternGeneratorHelper( List<String> finalSet,char [] pat,int recursiveCall){

if(recursiveCall==pat.length){
finalSet.add(new String(pat));
} else {
if(pat[recursiveCall]=='?'){
pat[recursiveCall]='0';
patternGeneratorHelper(finalSet,pat,recursiveCall+1);
pat[recursiveCall]='1';
patternGeneratorHelper(finalSet,pat,recursiveCall+1);
pat[recursiveCall]='?';
} else{
patternGeneratorHelper(finalSet,pat,recursiveCall+1);

}

}

}

public List<String> patternGenerator(String pattern){

List<String> finalSet = new ArrayList<String>();

patternGeneratorHelper(finalSet,pattern.toCharArray(),0);


return finalSet;
}

public void patternGeneratorHelper( List<String> finalSet,char [] pat,int recursiveCall){

        if(recursiveCall==pat.length){
            finalSet.add(new String(pat));
        } else {
            if(pat[recursiveCall]=='?'){
                pat[recursiveCall]='0';
                patternGeneratorHelper(finalSet,pat,recursiveCall+1);
                pat[recursiveCall]='1';
                patternGeneratorHelper(finalSet,pat,recursiveCall+1);
                pat[recursiveCall]='?';
            } else{
                patternGeneratorHelper(finalSet,pat,recursiveCall+1);

            }

        }

    }

    public List<String> patternGenerator(String pattern){

        List<String> finalSet = new ArrayList<String>();

        patternGeneratorHelper(finalSet,pattern.toCharArray(),0);


        return  finalSet;
    }

public void patternGeneratorHelper( List<String> finalSet,char [] pat,int recursiveCall){

        if(recursiveCall==pat.length){
            finalSet.add(new String(pat));
        } else {
            if(pat[recursiveCall]=='?'){
                pat[recursiveCall]='0';
                patternGeneratorHelper(finalSet,pat,recursiveCall+1);
                pat[recursiveCall]='1';
                patternGeneratorHelper(finalSet,pat,recursiveCall+1);
                pat[recursiveCall]='?';
            } else{
                patternGeneratorHelper(finalSet,pat,recursiveCall+1);

            }

        }

    }

    public List<String> patternGenerator(String pattern){

        List<String> finalSet = new ArrayList<String>();

        patternGeneratorHelper(finalSet,pattern.toCharArray(),0);


        return  finalSet;
    }

public void patternGeneratorHelper( List<String> finalSet,char [] pat,int recursiveCall){

        if(recursiveCall==pat.length){
            finalSet.add(new String(pat));
        } else {
            if(pat[recursiveCall]=='?'){
                pat[recursiveCall]='0';
                patternGeneratorHelper(finalSet,pat,recursiveCall+1);
                pat[recursiveCall]='1';
                patternGeneratorHelper(finalSet,pat,recursiveCall+1);
                pat[recursiveCall]='?';
            } else{
                patternGeneratorHelper(finalSet,pat,recursiveCall+1);

            }

        }

    }

    public List<String> patternGenerator(String pattern){

        List<String> finalSet = new ArrayList<String>();

        patternGeneratorHelper(finalSet,pattern.toCharArray(),0);


        return  finalSet;