CareerCup

I have two solutions. One with permutation and one without permutation using bitset.

#include "stdafx.h"
#include <iostream>
#include <string>
#include <set>
#include <bitset>

using namespace std;

set<string> perm;

void replace(string str, string strWith) {
int index = 0;
for(int i=0; i< str.length(); ++i) {
if(str[i] == '?') str[i] = strWith[index++];
}
cout << str << endl;
}

void parmutation(string str, string endStr) {
if(str.length() == 0) perm.insert(endStr);
for(size_t i = 0; i < str.length(); ++i) {
string StrIn = str;
string StrEnd = endStr;
StrIn.erase(i,1);
StrEnd += str.at(i);
parmutation(StrIn,StrEnd);
}
}

void replaceString(string str) {
perm.insert("0000");
parmutation("0001","");
parmutation("0011","");
parmutation("0111","");
perm.insert("1111");

for(auto it= perm.begin(); it != perm.end(); ++it) {
replace(str,*it);
}
}

void replaceWithPermutation(string str) {
for(int i=0; i< 16; ++i) {
bitset<4> bt(i);
replace(str,bt.to_string<char,string::traits_type,string::allocator_type>());
}
}

int main()
{
replaceString("a?b?c?d?");
cout << endl;
replaceWithPermutation("a?b?c?d?");
while(1) {}
return 0;
}

No Recursion needed.

Complexity: O(n) * no of combinations

The simplest way to solve this is to consider the number of diff combinations (num_of_comb) and representing that in binary starting from 0 to (num_of_comb - 1).

Ex a?b?c? has 8 comb. i.e 2^3 . i.e. 2 power no of '?'s. Obviously the possible combinations are 000, 001, 010, ..... 110, 111.

Complexity: O(n) * no of combinations.
O(n) to find no of '?'s.

Down below is the complete working code with minor description along. Comment if you can improvise further.

#include <iostream>
#include <cmath>
using namespace std;


void stringReplace ( char *str )
{
  char *temp = str;
  int count = 0, num_of_comb = 0, value = 0;

  while ( *temp ) {
    if ( *temp == '?' )
      count++;
    temp++;
  }
  temp = str;

  num_of_comb = pow(2,count);       // count the num of combinations
  cout << "There are " << num_of_comb << " different possible combinations";

  while ( value < num_of_comb ) {
    cout << endl;
    int calc = value;

    /* use the standard Math to convert num to its binary form, modify its output to the present context" */
    while ( *temp ) {
      if ( *temp == '?' ) {
        char ch = ( calc % 2 ) ? '1' : '0';
        calc /= 2;
        cout << ch << flush;  // do use 'flush' instead of unwanted 'newline' on Linux console to flush the buffer
      }

      else cout << *temp << flush;

      temp++;
    }

    temp = str;
    value++;
  }
}


int main ()
{
  char A[] = "????";      // makes it easy to see the combinations. You could obviously add letters
  stringReplace(A);
  while (1);
}

public static void replace(String str, int pos) {
		if (pos == str.length()) {
			System.out.println(str);
		}
		else if (str.charAt(pos) != '?'){
			replace(str, pos+1);
		}
		else {
			String prefix = str.substring(0, pos);
			String suffix = str.substring(pos+1);
			replace(prefix + "0" + suffix, pos+1);
			replace(prefix + "1" + suffix, pos+1);
		}
	}
	
	public static void replace(String str) {
		replace(str, 0);
	}

import java.util.ArrayList;


public class ReplaceQuestionMark {
    public ArrayList<String> replace(String target){
        return replaceHelper(target, target.length()-1);
    }

    public ArrayList<String> replaceHelper(String target, int to){
        char c = target.charAt(to);
        if (to == 0){
            ArrayList<String> res = new ArrayList<String>();
            if (c == '?'){
                res.add("0");
                res.add("1");
            }
            else{
                res.add(c+"");
            }
            return res;
        }
        ArrayList<String> res = new ArrayList<String>();
        ArrayList<String> preRes = replaceHelper(target, to-1);
        if (c == '?'){
            for (String token: preRes){
                res.add(token + "0");
                res.add(token + "1");
            }
        }
        else{
            for (String token: preRes){
                res.add(token + c);
            }
        }
        return res;
    }

    public static void main(String[] args){
        ReplaceQuestionMark rqm = new ReplaceQuestionMark();
        ArrayList<String> res = rqm.replace("a?b?c?");
        for (String s: res){
            System.out.println(s);
        }
    }
}

function doReplace(str) {
    if(str.indexOf('?') === -1) {
        return [str];
    } else {
        return []
            .concat(doReplace(str.replace(/(\?)/, '0')))
            .concat(doReplace(str.replace(/(\?)/, '1')));
    }
}

void Print(char p[], size_t len)
{
	for (int i = 0; i < len; ++i)
	{
		cout << p[i];
	}
	cout << endl;
}

bool Replace(char p[], size_t cur, char ch, size_t len)
{
	size_t pos = cur;
	for (; pos < len; ++pos)
	{
		if (p[pos] == '?')
		{
			break;
		}
	}
	if (pos < len)
	{
		p[pos] = ch;
		if (Replace(p, pos + 1, '0', len))
		{
			Replace(p, pos + 1, '1', len);
		}
		p[pos] = '?';
		return true;
	}
	else
	{
		Print(p, len);
		return false;
	}
}
void Replace(char p[], size_t len)
{
	if (Replace(p, 0, '0', len))
	{
		Replace(p, 0, '1', len);
	}

}

Tail recursive version in Scala:

import scala.util.matching.Regex._

val pattern = """([^?]*)\?""".r

def generate(text: String): List[String] = {
  val tokens = pattern.findAllMatchIn(text).toList.reverse
  if (tokens.isEmpty) {
    List(text)
  } else {
    val tail = text.drop(tokens.head.end)
    def helper(tokens: List[Match], acc: List[List[String]]): List[List[String]] = tokens match {
      case Nil => acc
      case token :: tail =>
        val text = token.group(1)
        helper(tail, (for (str <- acc) yield {
          List(text :: "0" :: str, text :: "1" :: str)
        }).flatten)
    }
    for (prefix <- helper(tokens, List(List("")))) yield {
      (prefix.iterator ++ tail).mkString("")
    }
  }
}

for (text <- List("aa?bb?cc", "aa?", "?aa", "aa", "?", "??", ""))
{
  println("Text: " + text)
  println(generate(text))
  println()
}

well you can try something like this....

String str = "a?b?c?";
 char[] arr = str.toCharArray();
 int occurrence = 0;
 List<Integer> index = new ArrayList<>();
 for (int i = 0; i < arr.length; i++) {
   if ('?' == arr[i]) {
       occurrence++;
       index.add(i);
      }
   }
 double twosPow = Math.pow(2, occurrence);
 List<String> list = new ArrayList<>();
 for (double i = 0; i < twosPow; i++) {
    int k = (int) i;
    String val = String.format("%" + occurrence + "s",
                              Integer.toBinaryString(k)).replace(" ", "0");
            list.add("" + val); // take binary
    }
 String replace = null;
 StringBuilder sb = null;
 List<String> result=new ArrayList<>();
 for (String i : list) {
     sb=new StringBuilder();
     sb.append(str);
     int p = 0;
     for (Integer k : index) {
          sb.replace(k, k+1, "" + i.charAt(p));
          p++;
         }              
          result.add(sb.toString());
        }
  System.out.println(result);

and the out put would be as..

[a0b0c0, a0b0c1, a0b1c0, a0b1c1, a1b0c0, a1b0c1, a1b1c0, a1b1c1]

public static void doReplace(String data){
long x = 0;
while(data.indexOf('?')>-1){
data = data.replaceFirst("\\?", "%s");
x++;
}

long max = (long)Math.pow(2, x);
if(max>1){
for(int i=0; i<max; i++){

String[] items = String.format("%"+x+"s",Integer.toBinaryString(i))
.replace(" ", "0")
.split("");

System.out.println(
String.format(data,
Arrays.copyOfRange(items,1,items.length)
)
);
}
}else{
System.out.println(data);
}

}

Here is the recursive approach:

void removeQm(char *s,int ind,int len)
{
	if(ind==len)
		return;
	if(s[ind]!='0'||s[ind]!='1')
	{
		ind=ind+1;
		removeQm(s,ind,len);
	}
	if(s[ind]=='0')
	{
		s[ind]='1';
		for(int i=0;i<len;i++)
			printf("%c",s[i]);
		printf("\n");	
		ind=ind+1;
		removeQm(s,ind,len);
	}
	if(s[ind]=='1')
	{
		s[ind]='0';
		for(int i=0;i<len;i++)
			printf("%c",s[i]);
		printf("\n");	
		ind=ind+1;
		removeQm(s,ind,len);
	}
		
}
int main()
{
	char s[]="a?b?c?d?";
	int len=strlen(s);
	for(int i=0;i<len;i++)
	{
		if(s[i]=='?')
			s[i]='0';
	}
	for(int i=0;i<len;i++)
		printf("%c",s[i]);
	printf("\n");
	removeQm(s,0,len);
}

void Print(char p[], size_t len)
{
for (int i = 0; i < len; ++i)
{
cout << p[i];
}
cout << endl;
}

bool Replace(char p[], size_t cur, char ch, size_t len)
{
size_t pos = cur;
for (; pos < len; ++pos)
{
if (p[pos] == '?')
{
break;
}
}
if (pos < len)
{
p[pos] = ch;
if (Replace(p, pos + 1, '0', len))
{
Replace(p, pos + 1, '1', len);
}
p[pos] = '?';
return true;
}
else
{
Print(p, len);
return false;
}
}
void Replace(char p[], size_t len)
{
if (Replace(p, 0, '0', len))
{
Replace(p, 0, '1', len);
}
}

One way of doing this is to generate the bits in-place and print the string once all the ‘?’ are replaced appropriately.

public static void printString (StringBuilder s, ArrayList<Integer> spots, int j){

	if (j==spots.size()){
		System.out.println(s.toString());
		return;
	}
	
	StringBuilder t = new StringBuilder ();
	char c=’0’;

	for (int i=0;i<2;i++){
		t.append(s.substring(0,spots.get(j)));
		t.append(c);
		t.append(s.substring(spots.get(j)+1));
		printString (t, spots, j+1);
		t.delete(0,t.length());
		c = ‘1’;
	}

}

public static void printString (StringBuilder s){
	ArrayList<Integer> spots = new ArrayList<Integer>();
	StringBuilder gen = new StringBuilder ();
	
	for (int i=0;i<s.length();i++)
		if (s.charAt(i) == ‘?’)
			spots.add(i);

	printString (s, spots, 0);
}

Below is java code:

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

public class StringReplace {
	
	public void replace(String string){
		
		List<Integer> questionMarkIndexList=new ArrayList<Integer>();
		for(int i=0;i<string.length();i++){
			if(string.charAt(i)=='?'){
				questionMarkIndexList.add(i);
			}
		}
		
		StringBuffer sb=new StringBuffer(string);
		
		doReplace(sb,questionMarkIndexList,0);
	}
	
	private void doReplace(StringBuffer sb,List<Integer> questionMarkIndexList ,int index){
		if(index>=questionMarkIndexList.size()){
			System.out.println(sb);
			return;
		}
		
		int questionMarkIndex=questionMarkIndexList.get(index);
		
		sb.setCharAt(questionMarkIndex, '0');
		doReplace(sb,questionMarkIndexList,index+1);
		
		sb.setCharAt(questionMarkIndex, '1');
		doReplace(sb,questionMarkIndexList,index+1);
		
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		String s="a?b?c?";
		
		StringReplace sr=new StringReplace();
		sr.replace(s);

	}

}

This is simple combinatorial algo

Print(string s)
{
       
       int ind = s.IndexOf('?');
       if(ind < 0)
        { 
           System.Out.Print(s);
	   return;
         }
       Print(s.Replateat(ind, '0');
  
       Print(s.Replaceat(ind, '1');
       
}

static List<string> Replace (string s)
        {
            var result = new List<string>(); 

            if (s == null)
                throw new ArgumentNullException();

            if (s.Length == 0)
                return result; 

            if (s.Length == 1)
            {
                if (s[0] == '?')
                    return new List<string> { "0", "1" };
                else
                    return new List<string> { s }; 
            }

            var items = s.Substring(1).Contains("?") ? Replace(s.Substring(1)) : new List<string> { s } ;
            foreach (var item in items)
            {
                if (s[0] == '?')
                {
                    result.Add(item.Insert(0, "0"));
                    result.Add(item.Insert(0, "1"));
                }
                else
                    result.Add(item.Insert(0, s[0].ToString()));
            }

            return result;
        }

import itertools,re

def generate_possible_strings(s, c):
    """
    :param s: input string
    :param c: matching character in our scenario ?
    returns : iterator by generating all possible results yields or None :
    """
    if re.search(c,s) == None:
        return
    rr = list(s)
    l_index, index_map = find_qm(s,c)
    # the possible combinations are all the subsets from 0 to 2**n-1
    for r in range(2**l_index):
        q = bin(r)[2:].zfill(l_index)
        for i, x in enumerate(q):
            rr[index_map[i]] = x
        yield ''.join(rr)

def find_qm(s,c):
    """
    :param s: input string
    :param c: matching character
    :return: a dictionary with the indexes for c in the string
    """
    index_map = {}
    for i, x in enumerate([m.start() for m in re.finditer(c, s)]):
        index_map[i] = x
    return len(index_map), index_map


if __name__ =='__main__':
    for r in generate_possible_strings(' a?b?c?tt?uu?','\?'):
        print r,

public class TestBuildGivenString {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		char a[] = "a?bc?def?g".toCharArray();
		printAllString(a, 0);
	}

	public static void printAllString(char[]a,int start)
	{
		int end = a.length-1;
		if(start >= end)
		{
			printArray(a);
			return;
		}
		
		for(int i=start;i<=end;i++)
		{
			if(a[i] == '?')
			{
				for(int j=0;j<=1;j++)
				{
					
						a[i] = (j+"").toCharArray()[0];
						printAllString(a, i+1);
						if(a[i] == '0' || a[i] == '1')
							a[i] = '?';
					
				}
				break;
			}
		
		}
	}
	
	public static int getLastIndex(char[]a,char c)
	{
		for(int i = a.length-1;i>=0;i--)
		{
			if(a[i] == c)
			{
				return i;
			}
		}
		
		return -1;
	}
	
	public static void printArray(char[]a)
	{
		StringBuffer buffer =  new StringBuffer();
		
		for(char c:a)
		{
			buffer.append(c);
		}
		System.out.println(buffer.toString());
		
	}
}

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

public class Replaceby0and1 {

public static void main(String[] args) {
String test = "a?b?ab?";
List<String> replacedStrings = replace(test);
for (String temp : replacedStrings) {
System.out.println(temp);
}

}

private static List<String> replace(String test) {

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

if (test.indexOf('?') == -1) {
replacedStrings.add(test);
return replacedStrings;
} else {

if (test.length() == 0) {
replacedStrings.add(test);
return replacedStrings;
} else if (test.length() == 1) {
if (test.equals("?")) {
replacedStrings.add("0");
replacedStrings.add("1");

} else {
replacedStrings.add(test);
}
return replacedStrings;
} else {

List<String> replacedSubStrings = new ArrayList<>();
replacedSubStrings = replace(test.substring(1, test.length()));
if (test.charAt(0) == '?') {
for (String temp : replacedSubStrings) {
replacedStrings.add('0' + temp);
replacedStrings.add('1' + temp);
}

} else {
for (String temp : replacedSubStrings) {
replacedStrings.add(test.charAt(0) + temp);

}
}

return replacedStrings;
}

}
}

}

public static void replaceChars(String s)
	{
		if((s==null)||(s.length()==0))
		{
			return;
		}
		int count=0;
		for(int i=0;i<s.length();i++)
		{
			if(s.charAt(i)=='?')
			{
				count++;
			}
		}
		if(count>0)
		{
			replaceWithPermutations(s,count,0);
		}
	}
	
	public static void replaceWithPermutations(String str, int count, int i)
	{
		if(count==0)
		{
			System.out.println(str);
		}
		else
		{
			if(str.charAt(i)=='?')
			{
				str = str.substring(0,i)+0+str.substring(i+1,str.length());
				replaceWithPermutations(str,count-1,i+1);
				str = str.substring(0,i)+1+str.substring(i+1,str.length());
				replaceWithPermutations(str,count-1,i+1);
			}
			else
			{
				replaceWithPermutations(str,count,i+1);
			}
		}

}

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

char *glob_str;
void rep_qm(char *inStr, int len);

int main(int argc, char* argv[])
{
  char* inStr;

  if(argc != 2)
  {
    printf("Usage: ./replace_qm <string>\n");
    return 0;
  }

  glob_str = inStr = argv[1];

  printf("Input String: %s\n", inStr);

  printf("Output Strings are: \n");
  rep_qm(inStr, strlen(inStr));

  return 0;
}

void rep_qm(char *inStr, int len)
{
  int i;

  //printf("rep_qm: str[%s] len[%d]\n", inStr, len);
  for(i=0;i<=len;i++)
  {
    if(inStr[i] == '?')
    {
      /*Replace the '?' with 0 first and continue for the remaining substring*/
      inStr[i] = '0';
      rep_qm((char *)&inStr[i+1], (len - i - 1));

      /*Then replace it with 1 and continue with remaining substring */
      inStr[i] = '1';
      rep_qm((char *)&inStr[i+1], (len - i - 1));

      /*Once done with every thing, replace the changed character back to '?' so that the position is not missed*/
      inStr[i] = '?';
        return;
    }
  }

  printf("%s\n",glob_str);

}

public void replaceMarkWith0and1(String str) {
        if (str == null) {
            throw new NullPointerException("Parameter passed is null");
        }

        if (str.isEmpty()) {
            System.out.println("String is empty");
            return;
        }

        char[] carray = str.toCharArray();
        printWithMark(carray, 0);
    }

    private void printWithMark(char[] str, int current) {
        if (str == null) {
            throw new NullPointerException("Parameter str is null");
        }

        if (current == str.length) {
            System.out.println(new String(str));
            return;
        }

        if (str[current] == '?') {
            str[current] = '0';
            printWithMark(str, current + 1);
            str[current] = '1';
            printWithMark(str, current + 1);
            str[current] = '?';
        } else {
            current++;
            printWithMark(str, current);
        }
    }

Recursive Program in Java:
public class ReplaceQuestionMark
{
public static void main(String[] args) {
String input = "a?b?c?";
replace(input.toCharArray());
}
public static void replace(char[] input) {
boolean found = false;
for(int i=0;i<2;i++) {
int foundAt = 0;
for(int j=0;j<input.length;j++) {
if(input[j] == '?') {
foundAt = j;
found = true;
break;
}
}
if(found) {
input[foundAt] = (char)(i + 48);
replace(input);
input[foundAt] = '?';
foundAt = 0;
}
else {
System.out.println(input);
return;
}
}
}
}

Recursive program in Java:

public class ReplaceQuestionMark {
	public static void main(String[] args) {
		String input = "a?b?c?";
		replace(input.toCharArray());
	}
	public static void replace(char[] input) {
		boolean found = false;
		for(int i=0;i<2;i++) {
			int foundAt = 0;
			for(int j=0;j<input.length;j++) {
				if(input[j] == '?') {
					foundAt = j;
					found = true;
					break;
				}
			}
			if(found) {
				input[foundAt] = (char)(i + 48);
				replace(input);
				input[foundAt] = '?';
				foundAt = 0;
			}
			else {
				System.out.println(input);
				return;
			}
		}
	}
}

I think my code will works.

import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

class Replace
{
private int[] number;
private List<Integer> indexlist;
char[] thestring;

public Replace(String s)
{
indexlist = new LinkedList<Integer>();
thestring = s.toCharArray();
int count = 0;
for(int i=0; i<thestring.length; i++)
{
if(thestring[i] == '?')
{
count++;
}
}

number = new int[count];

for(int i=0; i<count; i++)
{
number[i] = 0;
}

for(int i = 0; i<thestring.length; i++)
{
if(thestring[i] == '?')
{
indexlist.add(i);
}
}

}

public void output(char[] a)
{
System.out.println(a);
}

public void RemoveQ(int[] array, int start, int end)
{
if(start == end)
{
char[] result = new char[thestring.length];
int i = 0;
result = thestring.clone();
Iterator<Integer> iter = indexlist.iterator();
while(iter.hasNext())
{
result[iter.next()] = (char)(array[i]+48);
i++;
}

output(result);
return;
}
else
{
array[start] = 0;
RemoveQ(array, start+1, end);
array[start] = 1;
RemoveQ(array, start+1, end);
}
}


public void run()
{
int[] temp = new int[number.length];
temp = number.clone();
RemoveQ(temp, 0, temp.length);
}

}






public class Main {

public static void main(String args[])
{
Scanner in = new Scanner(System.in);
String instring = in.nextLine();
in.close();
Replace R = new Replace(instring);
R.run();
}

}

I think my code will works.

import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

class Replace
{
private int[] number;
private List<Integer> indexlist;
char[] thestring;

public Replace(String s)
{
indexlist = new LinkedList<Integer>();
thestring = s.toCharArray();
int count = 0;
for(int i=0; i<thestring.length; i++)
{
if(thestring[i] == '?')
{
count++;
}
}

number = new int[count];

for(int i=0; i<count; i++)
{
number[i] = 0;
}

for(int i = 0; i<thestring.length; i++)
{
if(thestring[i] == '?')
{
indexlist.add(i);
}
}

}

public void output(char[] a)
{
System.out.println(a);
}

public void RemoveQ(int[] array, int start, int end)
{
if(start == end)
{
char[] result = new char[thestring.length];
int i = 0;
result = thestring.clone();
Iterator<Integer> iter = indexlist.iterator();
while(iter.hasNext())
{
result[iter.next()] = (char)(array[i]+48);
i++;
}

output(result);
return;
}
else
{
array[start] = 0;
RemoveQ(array, start+1, end);
array[start] = 1;
RemoveQ(array, start+1, end);
}
}


public void run()
{
int[] temp = new int[number.length];
temp = number.clone();
RemoveQ(temp, 0, temp.length);
}

}






public class Main {

public static void main(String args[])
{
Scanner in = new Scanner(System.in);
String instring = in.nextLine();
in.close();
Replace R = new Replace(instring);
R.run();
}

}

Simple and concise recursive solution in Java.

public class PrintStrings {

    public static void main(String... args) {
        printStrings("a?bc?def?g");
    }

    private static void printStrings(String str) {
        printStrings(str, 0);
    }

    private static void printStrings(String str, int pos) {
        if (pos == str.length() - 1) {
            System.out.println(str);
            return;
        }

        for (; pos < str.length(); ++pos) {
            if (str.charAt(pos) == '?') {
                byte[] chars = str.getBytes();
                chars[pos] = '0';
                printStrings(new String(chars), pos + 1);
                chars[pos] = '1';
                printStrings(new String(chars), pos + 1);
                break;
            }
        }
    }
}

#!/usr/bin/python 
import itertools

text = 'ab?c?d?efg?'

def char_replace(string=""):
    count = string.count('?')
    snaps =  list(itertools.product(['0','1'],repeat=count)) 
    lst =[]
    #print snaps
    for snip in snaps:
        txt = list(string)
        for c in xrange(count):
            txt[txt.index('?')]=snip[c]
        lst.append("".join(txt))
    return lst
for x in char_replace(text):
    print x

public class careercup {
	private static String data = "a?bc?def?g";

	private static void get(int index, String counter) {
		if (index == data.length())
			System.out.println(counter);
		else if (data.charAt(index) == '?') {
			get(index + 1, "0" + counter);
			get(index + 1, "1" + counter);
		} else {
			get(index + 1, data.charAt(index) + counter);
		}
	}

	public static void main(String[] args) {
		get(0, "");
	}

}

Here code in C using recursion.

Code in C using recursion

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

static int N=0;
void generateComination( char *str ,int a[], int n){
  
     if(n ==0){ printf("%d->%s\n",++N,str);}
     else{
          str[a[n-1]]='0';
          generateComination(str,a,n-1);
          str[a[n-1]]='1';
          generateComination(str,a,n-1);
          }
          
     }
main(){
       char str[100];
       int i,j;
       int *ptr;
       int strlen=0,count=0,index=0;
       printf("Enter given string\n");
       scanf("%s",&str);
       printf("%s\n",str);
       i=0;
       while ( str[i] != '\0'){ i++; strlen++;}
       
      // printf("%d\n",strlen);
       for( i =0; i < strlen ; i++){  if(str[i] == '?')  count++; }
       //printf("%d\n",count);
       
       ptr=  (int *) malloc ( sizeof(int)* count);
       for( i =0; i < strlen ; i++){  
            if(str[i] == '?') { ptr[index++]= i;}
        }
       //for( i =0; i < index ; i++){ printf("%d",ptr[i]);}
       generateComination( str, ptr, count);
       
       int n;
       scanf("%d",&n);
}

void generator(vector<string> &ret, string s, size_t cur){
	if(cur==s.size()){
		ret.push_back(s);
		return;
	}
	if(s[cur]=='?'){
		s[cur]='0';
		generator(ret, s, cur+1);
		s[cur]='1';
		generator(ret, s, cur+1);
	}
	else
		generator(ret, s, cur+1);
}
void wrapperFillQuestionMark(){
	vector<string> ret;
	generator(ret, "a?b?c?", 0);
	for(auto it = ret.begin(); it!=ret.end(); ++it)
		cout << *it << endl;
}

void print_str_combinatins(const char *str){
    const char *p = str;
    unsigned int c, i;
    for(c = 0; *p; p++){
        if(*p == '?')
            c = c<<1 | 1; 
    }
    for(;c != 0; c--){
        for(p = str, i=c; *p; p++){
            if(*p == '?'){
                printf("%d", (i & 1));
                i >>= 1;
            } else {
                printf("%c", *p);
            }
        }
        printf("\n");
    }
    for(p = str, i=c; *p; p++){
        printf("%c", *p=='?' ? 0x30 : *p);
    }
}

How about this code?

public class Integer2Binary {
	public static void main(String[] args) {
		String str = "a?bc?def?gh?ij";
		char[] charArr = str.toCharArray();
		int count = 0;
		for(char c : charArr) {
			if(c == '?') {
				count++;
			}
		}
		String newStr = null;
		for(int i = 0; i < Math.pow(2, count); i++) {
			String bin = Integer.toString(i, 2);
			newStr = str;
			//System.out.println(newStr);
			while(bin.length() != count) {
				bin = "0" + bin;
			}
			//System.out.println(bin);			
			//String binPart = bin.substring(bin.length() - count, bin.length());
			char[] binPartArr = bin.toCharArray();
			
			for(char c : binPartArr) {
				newStr = newStr.replaceFirst("\\?", "" + c + "");
				//System.out.println(newStr);
			}
			System.out.println(newStr);
		}
	}
}

An iterative solution using bit manipulation (we want to replace the n ? with all the possible values of an n-bit vector).

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
using namespace std;

void gen_replace(string s) {
    stringstream ss(s);
    vector<string> tokens;
    
    //parse input string
    string elem;
    while(!ss.eof()) {
        getline(ss, elem, '?');
        tokens.push_back(elem);
    }
    int n_gaps = tokens.size() - 1 ;
    int n_combinations = ( 1 << n_gaps ); 

    //print all combinations
    for (int i = 1; i <= n_combinations; ++i) {
        int j=0;
        for (; j < n_gaps; ++j) {
            cout << tokens[j] << ((i >> j) & 1 ); 
        }
        cout << tokens[j] << endl; //print last token
    }
}

void ReplaceString(char* p, int index, int len)
{
    while (index < len && p[index] != '?')
        index++;

    if (index >= len)
    {
        printf("%s\n", p);
        return;
    }

    // we reached ? at index
    p[index] = '0';
    ReplaceString(p, index + 1, len);

    p[index] = '1';
    ReplaceString(p, index + 1, len);

    p[index] = '?';
}

int _tmain(int argc, _TCHAR* argv[])
{
    char s[] = "";
    ReplaceString(s, 0, strlen(s));
	return 0;
}

private static void generateValues(String s, int index) {
if (index == s.length()) {
System.out.println(s);
return;
}
for (int i= index; i < s.length(); i++) {
if (s.charAt(i) == '?') {
s = s.substring(0, i) + '0' + s.substring(i + 1);
generateValues(s, i + 1);
s = s.substring(0, i) + '1' + s.substring(i + 1);
generateValues(s, i + 1);
}
}
}

private static void generateValues(String s, int index) {
        if (index == s.length()) {
            System.out.println(s);
            return;
        }
        for (int i= index; i < s.length(); i++) {
            if (s.charAt(i) == '?') {
                s = s.substring(0, i) + '0' + s.substring(i + 1);
                generateValues(s, i + 1);
                s = s.substring(0, i) + '1' + s.substring(i + 1);
                generateValues(s, i + 1);
            }
        }
    }

<%
  # Ruby
  
  input = "a?b?c?d?e?f"
  @output = Array.new

  # replace ?'s with 0's
  input.gsub! "?", "0"
  @output << input

  # convert string to array and reverse
  @input_arr = input.chars.reverse

  # recursively iterate through array
  while idx_0 = @input_arr.index("0")
    @input_arr[idx_0] = "1"
    while idx_1 = @input_arr[0, idx_0].index("1")
      @input_arr[idx_1] = "0"
    end
    input = @input_arr.reverse.join
    @output << input
  end

  @output.join(", ")
%>

import java.util.ArrayList;

public class ReplaceQuestionMarks {

	//returns null if none
	public static ArrayList<String> replace(String original)
	{
		ArrayList<String> out = new ArrayList<String>();
		replaceHelper(original, 0, out);
		return out;
	}

	private static void replaceHelper(String s, int i, ArrayList<String> out)
	{
		if (i == s.length()) {
			out.add(s);
			return;
		}
		// else
		char[] cs = s.toCharArray();
		if (cs[i] == '?') {
			cs[i] = '0';
			replaceHelper(String.valueOf(cs), i+1, out);
			cs[i] = '1';
			replaceHelper(String.valueOf(cs), i+1, out);
		}
		else {
			replaceHelper(s, i+1, out);
		}
		return;
	}

	public static void main(String[] args)
	{
		String s = new String("a?b??");
		ArrayList<String> all = replace(s);
		for (String t : all) {
			System.out.println(t);
		}
	}
}

void replaceQnMarkByZeroOne(char *a,int i)
{
	if (a[i] == '\0')
	{
		puts(a);
		return ;
	}  
	while(a[i] != '?' )
	{
		i++;
		if(a[i] == '\0')
		 {
		 	puts(a); return;
		 } 
	
	}
	/* We get a Question Mark */
	a[i] = '0';
	replaceQnMarkByZeroOne(a, i+1);
	a[i] = '1';
	replaceQnMarkByZeroOne(a, i+1);
	
	// This is for back trace
	a[i]  = '?';
	
}

void test()
{
   char str[]="a?b?c?";
   replaceQnMarkByZeroOne(str,0);	
}

Code in Java

/**
 * Here is my algorithm without recursion.
 * It works faster and eats much less memory comparing to recursion.
 * The idea is that values 0 or 1 could be a bits of a number.
 * So we have to count symbol '?' and find a number of all possible combinations.
 * Combinations quantity is 2^(quantity of '?').
 * Then we make a loop and get a value of each bit for every number from loop.
 * Easy :)
 * Sorry for my english.
 */
public class Combinations {
    public static void main(String[] args) {
        String test = "a?b?c?d?";
        generator(test);
    }

    private static void generator(String str) {
        StringBuilder strB = new StringBuilder();
        boolean lastIsQMark = str.substring(str.length() - 1).equals("?");
        int bit;

        String arr[] = str.split("\\?");
        int bitsCount = arr.length - (lastIsQMark ? 0 : 1);
        int combinations = (int) Math.pow(2, arr.length - (lastIsQMark ? 0 : 1));

        for (int i = 0; i < combinations; i++) {
            for (int j = 0; j < bitsCount; j++) {
                bit = (i >> bitsCount - j - 1) & 1;
                strB.append(arr[j]);
                strB.append(bit);
            }

            if (!lastIsQMark) {
                strB.append(arr[bitsCount]);
            }

            System.out.println(strB.toString());
            strB.delete(0, strB.length());
        }
    }
}

public static List<String> generateString(char[] inputString, int startIndex) {
		List<String> result = new ArrayList<String>();
		StringBuilder sb = new StringBuilder();
		boolean addlast = true;
		for (int i = startIndex; i < inputString.length; i++) {
			if (inputString[i] != '?')
				sb.append(inputString[i]);
			else {
				List<String> otherResult = generateString(inputString, i + 1);
				for (String otherStr : otherResult) {
					result.add(sb.toString() + "0" + otherStr);
					result.add(sb.toString() + "1" + otherStr);
				}
				addlast = false;
				break;
			}
		}
		if (addlast)
			result.add(sb.toString());
		return result;
	}
        public static void main(String[] args) {
		char[] test = "?a?b??".toCharArray();
		for (String str : generateString(test, 0))
			System.out.println(str);

}

public static void replaceBits(String target) {
        int count = 0;
        List<Integer> charPositionList = new ArrayList<>();
        for (int i = 0; i < target.length(); i++) {
            if (target.charAt(i) == '?') {
                count++;
                charPositionList.add(i);
            }
        }
        StringBuilder finalString = new StringBuilder(target);
        for (int i = 0; i < (Math.pow(2, count)); i++) {
            String binaryString = Integer.toBinaryString(i);
            binaryString = "0000" + binaryString;
            binaryString = binaryString.substring(binaryString.length() - 4, binaryString.length());
            for (int j = 0; j < count; j++) {

                finalString.setCharAt(charPositionList.get(j), binaryString.charAt(j));

            }
            System.out.println(finalString);
        }
    }

C++ solution

void binarizeQuestionMarks(string str) {

    // find the indexes of question marks
    vector<int> stridxs;
    for (int i = 0; i < (int)str.size(); ++i) {
        if (str[i] == '?') {
            stridxs.push_back(i);
        }
    }

    // count from 0 to 2^strlen
    for (int i = 0; i < pow(2, (int)stridxs.size()); ++i) {
        // make appropriate assignment to each index
        for (int j = 0; j < (int)stridxs.size(); ++j) {
            // apply bitmask followed by bitshift to get 0 or 1
            int val = (i & (int)pow(2, j)) >> j;
            str[stridxs[j]] = '0' + val;
        }
        // output string
        cout << str << endl;
    }

}

C++ solution

void binarizeQuestionMarks(string str) {

    // find the indexes of question marks
    vector<int> stridxs;
    for (int i = 0; i < (int)str.size(); ++i) {
        if (str[i] == '?') {
            stridxs.push_back(i);
        }
    }

    // count from 0 to 2^strlen
    for (int i = 0; i < pow(2, (int)stridxs.size()); ++i) {
        // make appropriate assignment to each index
        for (int j = 0; j < (int)stridxs.size(); ++j) {
            // apply bitmask followed by bitshift to get 0 or 1
            int val = (i & (int)pow(2, j)) >> j;
            str[stridxs[j]] = '0' + val;
        }
        // output string
        cout << str << endl;
    }

}

#include<iostream>
    using namespace std;
  
	int QCnt = 0;

   void ADDval(char Input[], int flag, int Count)
   {
	   int i = 0;
	   int Val = QCnt - Count;

	   while(Input[i] != '\0')
	   {
		   if(Input[i] == '?' || Input[i] == '0' || Input[i] == '1')
		   {
			   if(Val == 0)
			   {
				Input[i] = flag + '0';
				break;
			   }
			   else Val --;
		   }
		   i++;
	   }
   }

   int CountQ(char Input[])
   {
	    int i = 0;	 
		int cnt = 0;

	   while(Input[i] != '\0')
	   {
		   if(Input[i] == '?')
		   {
			   cnt++;
		   }
		   i++;
	   }
   return cnt;
   }

   void ProcessString(char Input[],int Count)
   {
	   if(Count == 0)
	   {
		   cout<<Input<<endl;
	   }
	   else if(Count > 0)
	   {
		   ADDval(Input,0,Count);
		   ProcessString(Input,Count-1);
		   ADDval(Input,1,Count);
		   ProcessString(Input,Count-1);		   
	   }
   }


    int main()
    {
	
	char Input[] = {"a?b?c?"};
	int length = sizeof(Input)/sizeof(Input[0]);
	
	QCnt = CountQ(Input);
	
	ProcessString(Input,QCnt);

	getchar();
    return 0;
    }

List<string> Generate(string template) {

	var result = new List<string>();
	var current = template.ToArray();
	var index = new List<int>();
	for(int i=0; i<template.Length; i++) {
		if( template[i] == '?') {
			index.Add(i); //put index
			current[i] = '0'; //initial value
		}
	}

	result.Add( new string(current));
	var maxCount = 2 << index.Count;
	for( int n=1; n<8; n++) {
		var carry = true;
		for (var i=index.Count-1; i>=0; i--) {
			if( !carry)
				break;
			var pos = index[i];
			if( current[pos] == '1' ) { //max value
				current[pos] = '0';
				carry = true;
			}
			else { //was '0'
				current[pos] = '1';	
				carry = false;
			}
		}
		result.Add( new string(current));
	}
	return result;
}


var template = "a?bc?def?g";

Console.WriteLine(template);

var result = Generate(template);
Console.WriteLine("generated {0} strings", result.Count );
foreach (var s in result) {
    Console.WriteLine(s);
}

public class StringTest {
	static int row ,col,n;
	public String[][] buildGrid(String input) {
		n=0;
		String[][] matrix;
		col = input.length();
		for(int i=0; i<col; i++) {
			if(input.charAt(i)=='?')
				n++;
		}
		double m = Math.pow(2,n);
		row = (int) m;
		
		matrix = new String[row][col];
		return matrix;
	}
	
	public String[][] fillGrid(String input,String[][] Grid) {
		int d = 0;
		for(int a=0; a<col; a++){
			if(input.charAt(a)=='?'){
				d++;
				double m = Math.pow(2, d-1);
				double n = Math.pow(2, d);
				int p = (int) m;
				int q = (int) n;
				for(int i=0; i<p; i++) {		
					for(int j=(row/p*i); j<(row/q+row/p*i);j++){
						Grid[j][a] = "0";
						Grid[j+row/q][a] = "1";
					}
				}
			}
			else {
				for(int b=0; b<row; b++){
					char c = input.charAt(a);
					Grid[b][a]=String.valueOf(c);
				}
			}
		}
		return Grid;
	}
	
	public static void main(String[] args) {
		StringTest tmp = new StringTest();
		String input = "a?b?c?";
		String[][] preOutput = tmp.buildGrid(input);
		String[][] output = tmp.fillGrid(input,preOutput);
		for(int i=0; i<row; i++){
			for(int j=0; j<col; j++){
				System.out.print(output[i][j]);
			}
			System.out.println();
		}
	 }
}

public class StringTest {
	static int row ,col,n;
	public String[][] buildGrid(String input) {
		n=0;
		String[][] matrix;
		col = input.length();
		for(int i=0; i<col; i++) {
			if(input.charAt(i)=='?')
				n++;
		}
		double m = Math.pow(2,n);
		row = (int) m;
		
		matrix = new String[row][col];
		return matrix;
	}
	
	public String[][] fillGrid(String input,String[][] Grid) {
		int d = 0;
		for(int a=0; a<col; a++){
			if(input.charAt(a)=='?'){
				d++;
				double m = Math.pow(2, d-1);
				double n = Math.pow(2, d);
				int p = (int) m;
				int q = (int) n;
				for(int i=0; i<p; i++) {		
					for(int j=(row/p*i); j<(row/q+row/p*i);j++){
						Grid[j][a] = "0";
						Grid[j+row/q][a] = "1";
					}
				}
			}
			else {
				for(int b=0; b<row; b++){
					char c = input.charAt(a);
					Grid[b][a]=String.valueOf(c);
				}
			}
		}
		return Grid;
	}
	
	public static void main(String[] args) {
		StringTest tmp = new StringTest();
		String input = "a?b?c?";
		String[][] preOutput = tmp.buildGrid(input);
		String[][] output = tmp.fillGrid(input,preOutput);
		for(int i=0; i<row; i++){
			for(int j=0; j<col; j++){
				System.out.print(output[i][j]);
			}
			System.out.println();
		}
	 }
}

public class StringTest {
	static int row ,col,n;
	public String[][] buildGrid(String input) {
		n=0;
		String[][] matrix;
		col = input.length();
		for(int i=0; i<col; i++) {
			if(input.charAt(i)=='?')
				n++;
		}
		double m = Math.pow(2,n);
		row = (int) m;
		
		matrix = new String[row][col];
		return matrix;
	}
	
	public String[][] fillGrid(String input,String[][] Grid) {
		int d = 0;
		for(int a=0; a<col; a++){
			if(input.charAt(a)=='?'){
				d++;
				double m = Math.pow(2, d-1);
				double n = Math.pow(2, d);
				int p = (int) m;
				int q = (int) n;
				for(int i=0; i<p; i++) {		
					for(int j=(row/p*i); j<(row/q+row/p*i);j++){
						Grid[j][a] = "0";
						Grid[j+row/q][a] = "1";
					}
				}
			}
			else {
				for(int b=0; b<row; b++){
					char c = input.charAt(a);
					Grid[b][a]=String.valueOf(c);
				}
			}
		}
		return Grid;
	}
	
	public static void main(String[] args) {
		StringTest tmp = new StringTest();
		String input = "a?b?c?";
		String[][] preOutput = tmp.buildGrid(input);
		String[][] output = tmp.fillGrid(input,preOutput);
		for(int i=0; i<row; i++){
			for(int j=0; j<col; j++){
				System.out.print(output[i][j]);
			}
			System.out.println();
		}
	 }
}

public class StringTest {
	static int row ,col,n;
	public String[][] buildGrid(String input) {
		n=0;
		String[][] matrix;
		col = input.length();
		for(int i=0; i<col; i++) {
			if(input.charAt(i)=='?')
				n++;
		}
		double m = Math.pow(2,n);
		row = (int) m;
		
		matrix = new String[row][col];
		return matrix;
	}
	
	public String[][] fillGrid(String input,String[][] Grid) {
		int d = 0;
		for(int a=0; a<col; a++){
			if(input.charAt(a)=='?'){
				d++;
				double m = Math.pow(2, d-1);
				double n = Math.pow(2, d);
				int p = (int) m;
				int q = (int) n;
				for(int i=0; i<p; i++) {		
					for(int j=(row/p*i); j<(row/q+row/p*i);j++){
						Grid[j][a] = "0";
						Grid[j+row/q][a] = "1";
					}
				}
			}
			else {
				for(int b=0; b<row; b++){
					char c = input.charAt(a);
					Grid[b][a]=String.valueOf(c);
				}
			}
		}
		return Grid;
	}
	
	public static void main(String[] args) {
		StringTest tmp = new StringTest();
		String input = "a?b?c?";
		String[][] preOutput = tmp.buildGrid(input);
		String[][] output = tmp.fillGrid(input,preOutput);
		for(int i=0; i<row; i++){
			for(int j=0; j<col; j++){
				System.out.print(output[i][j]);
			}
			System.out.println();
		}
	 }
}

Basically I converted the number of ? on a binary number, from there I subtracted 1 and then I produce the string:

String cad = new String("a?b?c???");
		StringBuffer cad2 = new StringBuffer(cad);
		Integer num;
		String r;
		int i=0;
		int cont=0;
		int strLength, strLength2;
		while (i<cad.length()){
			if (cad.charAt(i)=='?') cont++;
			i++;
		}
		Double j = Math.pow(2, cont);
		num = new Integer(j.intValue()-1);
		System.out.println(num);
		strLength= num.toBinaryString(num).length();
		while (num.intValue()>=0){
			r = num.toBinaryString(num);
		//	System.out.println(r);
			num = new Integer(num.intValue()-1);
			i=0;
			cont=0;
			strLength2 = r.length();
			while(i<cad.length()){
				if (cad.charAt(i)=='?'){
					if (strLength==r.length()){
						cad2.setCharAt(i,r.charAt(cont));
						cont++;
					}
					else {
						if (strLength2<strLength){
							cad2.setCharAt(i,'0');
							strLength2++;
						}
						else {
							cad2.setCharAt(i,r.charAt(cont));
							cont++;
						}
					}
				}
				else cad2.setCharAt(i, cad.charAt(i));
				i++;
			}
			System.out.println(cad2);
			
		}

import java.util.*;
import java.lang.*;
class googleinterview
{
public static void main(String args[])
{
int count=0,r;
Scanner sc=new Scanner(System.in);
System.out.print("Enter the expression:");
String s=sc.next();
int len=s.length();
for(int i=0;i<s.length();i++)
{
if(s.charAt(i)=='?')
{
count++;
}
}
//System.out.println("Count="+count);
int power=(int)Math.pow(2,count);
//System.out.println("Power="+power);
int[][] a=new int[power][count];
int[][] b=new int[power][count];
int[] x=new int[power];
for(int i=0;i<power;i++)
{
x[i]=i;
}

for(int i=0;i<power;i++)
{
int k=0;
while(x[i]!=0)
{
r=x[i]%2;
//System.out.print(r);
a[i][k]=r;
x[i]=x[i]/2;
k++;
}

}
String s1=s;
System.out.println("**********Total possible combinations**********");
char[] ch=new char[len];
ch=s1.toCharArray();
for(int i=0;i<power;i++)
{
int k=count-1;
for(int j=0;j<len;j++)
{
if(s1.charAt(j)=='?')
{
if(k>=0)
{
System.out.print(a[i][k]);
k--;
}
else
break;
}
else
System.out.print(ch[j]);
}
System.out.println("\n");
}

}
}
/*
Output:
---------------------------------------------------
Enter the expression:?a?b?c
**********Total possible combinations**********
0a0b0c

0a0b1c

0a1b0c

0a1b1c

1a0b0c

1a0b1c

1a1b0c

1a1b1c

*/

public class CharacterReplacer {
	public static void main(String[] args) {
		String s = "a?b?c?djjjjh?";
		List<Integer> list = getNumberOfPosition(s);
		String[] str = generateCombination(s,list);
		for(String st : str){
			System.out.println(st);
		}
	}

	private static String[] generateCombination(String s, List<Integer> list) {
		String[] binaryCombination = getBinaryString(list);
		String[] allString = new String[binaryCombination.length];
		int index  = 0;
		for(String string : binaryCombination){
			StringBuffer stringBuffer = new StringBuffer(s);
			for(int k=0;k<list.size();k++){
				stringBuffer.replace(list.get(k), list.get(k)+1, string.substring(k,k+1));
			}
			allString[index++] = stringBuffer.toString();
		}
		return allString;
	}

	private static String[] getBinaryString(List<Integer> list) {
		int totalCombination = (int) Math.pow(2, list.size());
		String[] str = new String[totalCombination];
		for(int i = 0 ; i < totalCombination;i++){
			str[i] = Integer.toBinaryString(i);
			int diff = list.size() - str[i].length();
			String s = "";
			for(int j=0 ; j<diff ; j++)
				s =s + "0";
			str[i] = s + str[i];
		}
		return str;
	}

	private static List<Integer> getNumberOfPosition(String s) {
		char[] ch = s.toCharArray();
		List<Integer> list = new ArrayList<>();
		for(int i = 0;i < ch.length;i++){
			if(ch[i] == '?'){
				list.add(i);
			}
		}
		return list;
	}
}

public void getAllPossible(String original_string ){
		
		
		getAllPossible(original_string , "" , 0);
	}

	
	
	public void getAllPossible(String original_string , String made_String , int index ){
		
		char two [] = {'0' , '1'};
		
		
		for(int i=index;i<original_string.length();i++){
			
			if(original_string.charAt(index)=='?'){
				
				for(char s: two){
					getAllPossible(original_string, made_String+s , index+1);
				}
			}else{
				
				made_String+=original_string.charAt(index);
			}
			
			
		}
		
		if(made_String.length()==original_string.length()){
			System.out.println(made_String);
		}
		
	}

vector<string> writeReplacements(const string &initialString)
{
	vector<string> allReplacements;

	const int questionCount = count(initialString.begin(), initialString.end(), '?');
	const int variantsCount = 2 << (questionCount-1);
	for (int i = 0; i < variantsCount; i++)
	{
		string str = initialString;
		int questionCounter = 0;
		for (int j = initialString.size()-1; j >= 0; j--)
		{
			if (initialString[j] == '?')
			{
				str[j] = '0' + (i >> questionCounter) % 2;
				questionCounter++;
			}
		}
		allReplacements.push_back(str);
	}

	return allReplacements;
}

Not the best solution, but its another one

public static void main(String[] args) {
		ArrayList<String> result = combify("a?bc?def?g");
		for (String r : result ) System.out.println(r);
	}
	
	private static ArrayList<String> combify(String string) {
		ArrayList<String> result = new ArrayList<String>();
		ArrayList<Integer> positions = new ArrayList<Integer>();
		for ( int index = 0; index < string.length(); index++ ) {
			if (string.charAt(index) == '?' )
				positions.add(index);
		}
		
		long combo = Math.round(Math.pow(2, positions.size()));
		for ( int value = 0; value < combo; value++ ) {
			String copy = string;
			for ( int times = 0; times < positions.size(); times++ ) {
				long val = 0x01 & (value >> times);
				copy = copy.replaceFirst("\\?", "" + val);
			}
			result.add(copy);
		}
		
		return result;
	}

public static void main(String[] args) {
	 
        ArrayList<String> result = new ArrayList<String>();
        String s = "a?bc?def?g";
        replace(s,result);

        for(String ss:result){
        	System.out.println(ss);
        }			
}

public static void replace(String s,ArrayList<String> result){
		String[] sp = s.split("\\?");
		String[] set = {"0","1"};
		String res = "";
		replaceHelper(sp,0,set,res,result);
		
	}
	public static void replaceHelper(String[] s, int index,String[] set,String res,ArrayList<String> result){
		if(s.length < 1)
			return;
		
		if(index == (s.length-1)){
			result.add(res+s[index]);
			return;
		}
		
		for(int j=0;j<set.length;j++){
			String temp = res + s[index]+set[j];
			replaceHelper(s,index+1,set,temp,result);
		}
			
	}

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

int main()
{
         char str[20] = "a??b??c?";
        int i = 0, z ;
        int count  = 0 , occ = 0;
        int bit = 1, d;
        int index[10];
         while(str[i]!='\0')
        {
                 if(str[i] == '?')
                {
                        index[count] = i;
                        count++;
                }
                i++;
        }
        occ = count;
        while(count)
        {
                bit = bit * 2; //bit = 8
                 count--;
         }
         i=0;
        bit = bit - 1;
         while(i<=bit)
         {
                 d = 0;
                for (z = 1<<occ-1 ; z > 0; z >>= 1)
                {
                        if((i & z)==z)
                         {
                                str[index[d]] = '1';
                         }
                         else
                         {
                                 str[index[d]] = '0';
                         }
                        d++;
                 }
                i++;
                printf("\n String = %s\n ",str);
        }
        return 0;
}

#include<iostream>

using namespace std;

void generate(string& iStr , int index)
{
    if(index == iStr.size())
	{
		cout<<"\n"<<iStr;
	}
	else 
	{
		if(iStr[index] == '?')
		{
			iStr[index] = '0';
			generate(iStr , index + 1);
			iStr[index] = '1';
			generate(iStr , index + 1);
            iStr[index] = '?';
		}
		else
		{
			generate(iStr , index + 1);	
		}
	}
}

void generate(string iStr)
{
	generate(iStr , 0);
}

int main()
{
	generate("a?bc?def?g");
}

public class StringReplacer {

private String input;

public StringReplacer(String in) {
this.input = in != null ? in : "?";
}

public String[] replace() {
int count = 0, size = 0;

for (char c : this.input.toCharArray()) {
if (c == '?') {
size = 1<<(++count);
}
}

String[] out = new String[size];
int replacer = size;
replacer--;
for (int z=0; z<size; z++,replacer--) {
String replacerString = Integer.toBinaryString(replacer);
while (replacerString.length()<count) {
replacerString = "0"+replacerString;
}

int c=0;
char[] chars = this.input.toCharArray();
for (int p=0; p<chars.length; p++) {
if (chars[p] == '?') {
chars[p] = replacerString.charAt(c++);
}
}


out[z] = new String(chars);
}

return out;

}

public static void main(String[] args) {
StringReplacer replacer = new StringReplacer("a?b?c?");

String[] replaced = replacer.replace();

for (String s : replaced) {
System.out.println(s);
}
}

}

public class Question {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		questionReplace("a?bc?def?g");
	}
	
	public static void questionReplace(String question){
		
		int count = 0;
		for(int i = 0; i < question.length(); i++){
			if(question.charAt(i) == '?'){
				count++;
			}
		}
	
		String[] s = new String[(int)Math.pow(2,count)];
		for(int i = 0; i < s.length; i++){
			s[i] = "";
		}
		zeroOne(s);
		
		for(int i = 0; i < Math.pow(2,count); i++){
			int counter = 0;
			int subIndex = 0;
			String sub = "";
			for(int j = 0; j < question.length(); j++){
				if(question.charAt(j) == '?'){
					sub +=  question.substring(subIndex, j) + s[i].charAt(counter);
					subIndex = j + 1;
					counter++;
				}
				if(counter == Math.log(s.length) / Math.log(2)){
					sub += question.substring(subIndex, question.length());
					break;
				}
			}
			System.out.println(sub);
		}
	}
		
	public static void zeroOne(String[] a){
		
		int n = (int)( Math.log(a.length) / Math.log(2));
		int N = a.length;
		for(int i = 0; i < n; i++){
			int count = 0;
			int secCount = 0;
			for(int j = 0; j < a.length; j++){
				if(count < N/2){  
					a[j] += 0 + "";
					secCount = 0;
					count++;
				}
				else{  
					secCount++;
					a[j] += 1 + ""; 
				}
				if(secCount == N/2){
					count= 0;
				}
			} 
			N /= 2;
		}
	}
}

public class Question {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		questionReplace("a?bc?def?g");
	}
	
	public static void questionReplace(String question){
		
		int count = 0;
		for(int i = 0; i < question.length(); i++){
			if(question.charAt(i) == '?'){
				count++;
			}
		}
	
		String[] s = new String[(int)Math.pow(2,count)];
		for(int i = 0; i < s.length; i++){
			s[i] = "";
		}
		zeroOne(s);
		
		for(int i = 0; i < Math.pow(2,count); i++){
			int counter = 0;
			int subIndex = 0;
			String sub = "";
			for(int j = 0; j < question.length(); j++){
				if(question.charAt(j) == '?'){
					sub +=  question.substring(subIndex, j) + s[i].charAt(counter);
					subIndex = j + 1;
					counter++;
				}
				if(counter == Math.log(s.length) / Math.log(2)){
					sub += question.substring(subIndex, question.length());
					break;
				}
			}
			System.out.println(sub);
		}
	}
		
	public static void zeroOne(String[] a){
		
		int n = (int)( Math.log(a.length) / Math.log(2));
		int N = a.length;
		for(int i = 0; i < n; i++){
			int count = 0;
			int secCount = 0;
			for(int j = 0; j < a.length; j++){
				if(count < N/2){  
					a[j] += 0 + "";
					secCount = 0;
					count++;
				}
				else{  
					secCount++;
					a[j] += 1 + ""; 
				}
				if(secCount == N/2){
					count= 0;
				}
			} 
			N /= 2;
		}
	}
}

In Ruby:
Assume there are 3 question marks, use binary string from 000 to 111. Convert it to string, replace binary chars with each question marks.

# s = "a?bc?def?g", 3 question marks
def fill_qmarks_iterate( s )
  count_q = s.chars.count("?")
  n = 2 ** count_q # n = 1000 to 1111
  for x in n..n*2-1
    s2 = s.clone
    # from 000 to 111
    x.to_s(2).chars[1..s.chars.count("?")].each do |y|
      s2[ s2.index("?") ] = y # replace with first ? from left
    end
    p s2
  end
end

Backtracking in C++:

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

void generate(int depth, string gen, string &s){
    if (depth == (int)s.size()){
        cout << gen << endl;
    }
    else{
        if(s[depth] == '?'){
            generate(depth + 1, gen + '0', s);
            generate(depth + 1, gen + '1', s);
        }
        else {
            generate(depth + 1, gen + s[depth], s);
        }
    }
}

int main(){
    string s;
    cin >> s;
    generate(0, "", s);

    return 0;
}

public static List<String> combinations(String input) {
		List<String> resultSet = new ArrayList<String>();
		
		Stack<String> stack = new Stack<String>();
		stack.push(input);
		while (!stack.isEmpty()) {
			String current = stack.pop();
			if (current.indexOf("?") == -1) {
				resultSet.add(current);
			} else {
				stack.push(current.replaceFirst("\\?", "0"));
				stack.push(current.replaceFirst("\\?", "1"));
			}
		}
		
		return resultSet;
	}

public class Sequence {

	private static void allSequence(String str, int replaced, int zeros,
			int ones) {

	

		if (replaced == 3) {
			System.out.println( str);
			return;
		}

		if (zeros > 0 && replaced < 3) {

			StringBuilder sb = new StringBuilder();
			boolean change = false;
			for (int i = 0; i < str.length(); i++) {

				if (str.charAt(i) == '$' && !change) {
					sb.append("0");
					change = true;
				} else {
					sb.append(str.charAt(i));
				}
			}

			allSequence(sb.toString(), replaced + 1, zeros - 1, ones);
		}

		if (ones > 0 && replaced < 3) {

			StringBuilder sb = new StringBuilder();
			boolean change = false;
			for (int i =0 ; i < str.length(); i++) {

				if (str.charAt(i) == '$' && !change) {
					sb.append("1");
					change = true;
				
				} else {
					sb.append(str.charAt(i));
				}
			}
			allSequence(sb.toString(), replaced + 1, zeros, ones - 1);

		}

	}

	public static void main(String[] args) {

		allSequence("a$b$c$", 0, 3, 3);

	}
}

void interrogant_to_0_and_1(const std::string& string, int pos)
{
	if (pos >= string.size())
		std::cout << string.c_str() << std::endl;
	else if (string[pos] == '?')
	{
		std::string new_string = string;
		new_string[pos] = '0';
		interrogant_to_0_and_1(new_string, pos + 1);
		new_string[pos] = '1';
		interrogant_to_0_and_1(new_string, pos + 1);
	}
	else
		interrogant_to_0_and_1(string, pos + 1);
}

void interrogant_to_0_and_1(const std::string& string)
{
	// Recursive approach
	interrogant_to_0_and_1(string, 0);
}

Java solution - no recursion. Memory O(n), does n * 2^n operations.

public static void main(String[] args) {
        String input = "ab?asd?asdfasdf??saf???sadf????";
        int numMarks = 0;

        for (char c : input.toCharArray()) {
            if (c == '?') {
                numMarks++;
            }
        }

        for (int i = 0; i < Math.pow(2, numMarks); i++) {
            String variant = new String(input);
            int markNumber = 0;
            for (int j = 0 ; j < input.length(); j++) {
                if (input.charAt(j) == '?') {
                    markNumber++;
                    if ((i & markNumber) > 0) {
                        variant = variant.substring(0, j) + '1' + variant.substring(j+1);
                    } else {
                        variant = variant.substring(0, j) + '0' + variant.substring(j+1);
                    }
                }
            }
            System.out.println(variant);
       }
    }

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

int main(){
  string tmp;

  cin >> tmp;
  vector<int> pos;
  int found=0;
  for (int i=0; i<tmp.size();i++){
    if (tmp[i]=='?'){
     found++;
     pos.push_back(i);
    }
  }
  for (int i=0;i<(1<<found);i++){
    for (int j=0;j<pos.size();j++){
      tmp[pos[j]]=(i&(1<<j))?'1':'0';
    }
    cout <<tmp<<endl;
  }

  return 0;
}

Here is simple readable code with working solution using recursion. Just copy paste and compile

public class aqbqcq {
public static void main(String[] args)
{
replace("a?b?c?d?");
}

public static void replace(String s)
{
char c;

for (int i = 0; i < s.length(); i++)
{
c = s.charAt(i);

if (c == '?')
{
replace(rc(s,i,'0'));
replace(rc(s,i,'1'));
return;
}
}

System.out.println(s);
}

// Replace char in string at certain index
public static String rc(String s, int index, char c)
{
return s.substring(0,index) + c + s.substring(index+1);
}
}

using System;
using System.Text;

namespace SRMs
{
    public class StringGames
    {
        public void AllStrings(string template)
        {
            int counter = 0;
            for (int i = 0; i < template.Length; i++)
            {
                if (template[i] == '?')
                {
                    counter++;
                }
            }
            
            long numberOfCombinations = 1 << counter;
            for (long i = 0; i < numberOfCombinations; i++)
            {
                var result = new StringBuilder();
                int move = 0;
                for (int j = 0; j < template.Length; j++)
                {
                    if (template[j] == '?')
                    {
                        result.Append((i & (1 << move++)) == 0
                            ? "0"
                            : "1");
                    }
                    else
                    {
                        result.Append(template[j]);
                    }
                }
                Console.WriteLine(result);
            }
        }
    }
}

Works in cases where number of '?' is less then 63.

using System;
using System.Collections.Generic;

namespace InterviewTasks
{
    internal static class QuotationMarks
    {
        public static string[] GetAllStrings(string pattern)
        {
            if (string.IsNullOrEmpty(pattern))
            {
                throw new ArgumentException("Pattern should be a non-empty string");
            }

            List<int> quotationMarks = new List<int>();
            for (int i = 0; i < pattern.Length; ++i)
            {
                if (pattern[i] == '?')
                {
                    quotationMarks.Add(i);
                }
            }

            string[] result = new string[1 << quotationMarks.Count];
            for (int i = 0; i < result.Length; ++i)
            {
                char[] chars = pattern.ToCharArray();
                for (int j = 0; j < quotationMarks.Count; ++j)
                {
                    var quotationMarkPosition = quotationMarks[j];
                    chars[quotationMarkPosition] = ((i >> j) & 1) == 1 ? '1' : '0';
                }
                result[i] = new string(chars);
            }

            return result;
        }
    }
}

final double LOG_2 = Math.log(2);
        String a = "b????a";
        int numOfQues = 0;
        for(int i = 0; i<a.length();i++){
            if(a.charAt(i) == '?'){
                numOfQues++;
            }
        }
        ArrayList<Boolean[]> bitMasks= new ArrayList<Boolean[]>();
        for(int i = 0; i <(1<<numOfQues); i++){
            int x = i;
            Boolean bitMsk[] = new Boolean[numOfQues];
            Arrays.fill(bitMsk, false);
            while(x!=0){
                //get least significant bit
                int tar = (int) (Math.log(x & ~(x-1))/LOG_2);
                bitMsk[tar] = true;
                //remove least significant bit:
                x = x & (x-1);
            }
            bitMasks.add(bitMsk);
        }
        for(int i = 0; i<bitMasks.size(); i++){
            for(int l = 0; l< bitMasks.get(i).length; l++){
                System.out.print((bitMasks.get(i)[l] == true ? 1 : 0) + " ");
            }
            System.out.println();
        }

        for(int i = 0; i<bitMasks.size(); i++){
            int index = 0;
            for(int l = 0; l<a.length(); l++){
                if(a.charAt(l) == '?'){
                    System.out.print(bitMasks.get(i)[index++] == true ? 1 : 0);
                }else{
                    System.out.print(a.charAt(l));
                }
            }
            System.out.println();
        }

No recursion, extra O(n) space

public static void main(String[] args) {
        compute("a?b?c?");
    }

    public static void compute(String s)
    {
        List<Integer> questionPosition = new ArrayList<>();
        for(int i=0;i<s.length();i++) {
            char character = s.charAt(i);
            if(character == '?') {
                questionPosition.add(i);
            }
        }
        
        //for faster modification than String
        char[] inputArray = s.toCharArray();
        //to know when to end
        int numberOf1s =0;
        //which questionmark to process next
        int currentQuestion=0;

        while(numberOf1s < questionPosition.size()) {
            if(currentQuestion<questionPosition.size()) {
                char q = inputArray[questionPosition.get(currentQuestion)];
                if(q == '?') {
                    inputArray[questionPosition.get(currentQuestion)] = '0';
                    currentQuestion++;
                } else if(q=='0'){
                    inputArray[questionPosition.get(currentQuestion)] = '1';
                    numberOf1s++;
                    currentQuestion++;
                } else if(q=='1') {
                    inputArray[questionPosition.get(currentQuestion)] = '?';
                    numberOf1s--;
                    currentQuestion--;
                }
            } else {
                printArray(inputArray);
                currentQuestion--;
            }

        }
        // last 1's were not printed
        printArray(inputArray);
    }

    private static void printArray(char[] inputArray)
    {
        for(int i=0;i<inputArray.length;i++) {
            System.out.print(inputArray[i]);
        }
        System.out.println();
    }

import java.util.List;

/**
 * Created by tiwariaa on 7/5/15.
 */
public class StringCombination {

    public static void printStringCombincation(String arg){
        if(!arg.contains("?"))
            System.out.println(arg);
        String with1s = arg.replaceAll("\\?", "1");
        String with0s = arg.replaceAll("\\?", "0");
        for(int i=0; i<with1s.length(); i++){
           if(with1s.charAt(i) == '1'){
            System.out.println(with1s.substring(0, i) + "0" + with1s.substring(i + 1));
           }
        }

        for(int i=0; i<with0s.length(); i++){
            if(with0s.charAt(i) == '0'){
                System.out.println(with0s.substring(0, i) + "1" + with0s.substring(i + 1));
            }
        }

    }

    public static void main(String[] args){
        if(args.length == 0){
            System.out.println("Please pass right args");
            return;
        }

        printStringCombincation(args[0]);
    }
}

void print01Helper(char* s, int i)
{
	if (i == -1)
	{
		printf("%s\n", s);
		return;
	}

	if (s[i] == '?')
	{
		s[i] = '0';
		print01Helper(s, i - 1);
		s[i] = '1';
		print01Helper(s, i - 1);
		s[i] = '?';
	}
	else
	{
		print01Helper(s, i - 1);
	}
}

void print01(char* s)
{
	print01Helper(s, strlen(s) - 1);
}

void print01Helper(char* s, int i)
{
	if (i == -1)
	{
		printf("%s\n", s);
		return;
	}

	if (s[i] == '?')
	{
		s[i] = '0';
		print01Helper(s, i - 1);
		s[i] = '1';
		print01Helper(s, i - 1);
		s[i] = '?';
	}
	else
	{
		print01Helper(s, i - 1);
	}
}

void print01(char* s)
{
	print01Helper(s, strlen(s) - 1);
}

/*void calcPermutation(int n, vector<vector<int>> &permutationArr)
{
	if (n <= 0)
	{
		return;
	}

	//if n = 2, nTemp = 3
	//if n = 3, nTemp = 7
	//if n = 4, nTemp = 15
	//.... 

	int nTemp = (int)pow(2, n);
	
	permutationArr.resize(nTemp);
	for (int i = 0; i < nTemp; i++)
		permutationArr[i].resize(n);
	
	nTemp--;

	int p, q;

	p = 0;
	q = 0;

	for (int i = 0; i <= nTemp; i++)
	{
		for (int k = 0; k < n; k++)
		{
			if ((i >> k) & 0x1)
			{
				permutationArr[p][q] = 1;
			}
			else
			{
				permutationArr[p][q] = 0;
			}

			if (k != n - 1)
			{
				q++;
			}
		}

		p++;
		q = 0;
	}
}
*/

void calcPermutation(int n, vector<vector<int>> &permutationArr)
{
	if (n <= 0)
	{
		return;
	}

	//if n = 2, nTemp = 3
	//if n = 3, nTemp = 7
	//if n = 4, nTemp = 15
	//.... 

	int nTemp = (int)pow(2, n);

	permutationArr.resize(nTemp);
	for (int i = 0; i < nTemp; i++)
		permutationArr[i].resize(n);


	int val = 0;
	int p, q, calc;

	p = 0;
	

	while (val < nTemp)
	{
		q = 0;
		calc = val;
		while (q < n)
		{
			permutationArr[p][q] = calc % 2 ? 0 : 1;
			calc = calc/2;
			q++;
		}
		p++;
		val++;
	}

}


void replaceString(string input)
{
	int i,j;
	int len = strlen(input.c_str());
	int qCount = 0;
	int *qIndexArr = new int[len];

	j = 0;
	for (i = 0; i < len; i++)
	{
		if (input[i] == '?')
		{
			qIndexArr[j] = i;
			j++;
			qCount++;
		}
	}

	if (qCount == 0)
	{
		cout << input << endl;
		return;
	}

	vector<vector<int>> permutationArr;		
	calcPermutation(qCount, permutationArr);
	list<string> l;
	char *temp = new char;

	for (i = 0; i < permutationArr.size(); i++)
	{
		for (j = 0; j < qCount; j++)
		{
			 temp = itoa(permutationArr[i][j],temp, 10);
			input[qIndexArr[j]] = *temp;
		}
		l.push_back(input);
	}

	list<string>::iterator it;

	cout << "Answers is:";
	for (it = l.begin(); it != l.end(); ++it)
	{
		std::cout << ' ' << *it;
		std::cout << '\n';
	}
	
}


int main(int argc, char* argv[])
{
	replaceString("a?b?c?");
	return 0;
}

I came up with this code: I think it runs in O(N.2^K). K is number of combos. Any Suggestions?

Queue<String> q = new LinkedList<String>();
		q.add(s);
		while(!q.isEmpty())
		{
			String ns = q.poll();
			int replaceIndex = ns.indexOf('?');
			if(replaceIndex > -1)
			{
				String ss1 = ns.substring(0, replaceIndex);
				String ss2 = ns.substring(replaceIndex+1, ns.length());
				String ns1 = ss1+"0"+ss2;
				String ns2 = ss1+"1"+ss2;
				q.add(ns1);q.add(ns2);
			}
			else
				System.out.println(ns);
		}

public static String[] convertAll(String input) {

// Find amount of ?
int amountOfQuestionMarks = 0;
for (char c : input.toCharArray()) {
if (c == '?') amountOfQuestionMarks++;
}

// If no question marks return empty array
if (amountOfQuestionMarks == 0) return new String[]{};

int variations = (int) Math.pow(2, amountOfQuestionMarks);
String[] result = new String[variations];

for (int i = 0; i < variations; i++) {
String binaryString = Integer.toBinaryString(i);
if (binaryString.length() < amountOfQuestionMarks) {
String zeroStrings = getZeroStrings(amountOfQuestionMarks, binaryString.length());
binaryString = zeroStrings + binaryString;
}

char[] binaryChars = binaryString.toCharArray();
String modifiedInput = input;
for (char c : binaryChars) {
modifiedInput = modifiedInput.replaceFirst("\\?", Character.toString(c));
}

result[i] = modifiedInput;
}

return result;
}

private static String getZeroStrings(int shouldBe, int current) {
StringBuilder builder = new StringBuilder();
for (int i = 0; i < shouldBe - current; i++) {
builder.append('0');
}
return builder.toString();
}

Code in C:

#include <stdio.h>

/*
 * src is the source string which containing target to be replaced
 * offset is where to start this replace action in source string
 * target is target character to be found and replaced
 * candidate is an array of all substitutes
 * n is the size of candidate array
 */
void permutateReplace(char* src, int offset, char target,
                      const char candidate[], int n
)
{
//step 1: find the first target start from offset
    for(; src[offset]; ++offset){
        if(src[offset] == target) break;
    }
//step 2: if found, use candidate to replace it, else print the result out
    if(src[offset]){
        //try to replace target with every candidate
        int i = 0;
        for(; i < n; ++i){
            src[offset] = candidate[i];
            permutateReplace(src, offset + 1, target, candidate, n);
        }
        //restore site
        src[offset] = target;
    }
    else puts(src);
}

int main()
{
    char src[] = "a?b?c?";
    char target = '?';
    char candidate[] = {'0', '1'};
    
    permutateReplace(src, 0, target, candidate, sizeof(candidate)/sizeof(char));
    
    return 0;
}

#!/usr/bin/env python
import string
import sys
def comb(s):
c = s.lower().count('?')
for i in range(c ** 2 -1 ):
l1 = list(bin(i)[2:].zfill(c))
s1 = s[:]
for j in range(c):
s1 = string.replace(s1,'?', l1[j], 1)
print s1

if __name__ == "__main__":
s = sys.argv[1]
comb(s)

play.google.com/store/apps/details?id=com.couponkart.couponcodes

try this out . might be useful

play.google.com/store/apps/detai...
try it out