Given a string (for example: "a?bc?def?g"), write a program to generate all the possible strings by replacing ? with 0 and 1.

Input : a?b?c? 
Output: a0b0c0, a0b0c1, a0b1c0, a0b1c1, a1b0c0, a1b0c1, a1b1c0, a1b1c1.

I have developed a program as shown below but please advise if something more efficiently can be done.

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 == '?'){
            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");
            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){
  • \$\begingroup\$ What is happening?. Do you have a problem in the code? . \$\endgroup\$ Commented Aug 18, 2014 at 11:46
  • 1
    \$\begingroup\$ If your code is working, this would do better over at codereview.SE. \$\endgroup\$
    – Quirliom
    Commented Aug 18, 2014 at 11:47
  • \$\begingroup\$ See binary numbers in output, you will find alternative approach \$\endgroup\$
    – Adi
    Commented Aug 18, 2014 at 11:51
  • \$\begingroup\$ Assuming this is homework, this can be done more compact and lacks self-explanatory names (helper, preres). Also consider an empty string as input. \$\endgroup\$
    – Joop Eggen
    Commented Aug 18, 2014 at 12:00
  • 1
    \$\begingroup\$ That is certainly a complicated way to do it. Unless you were told to use a recursive algorithm, I'd simply count the ? characters, then count from zero to 2^N to generate the ones and zeros. \$\endgroup\$
    – Hot Licks
    Commented Aug 18, 2014 at 12:06

3 Answers 3


An easy way to generate all of the possible 0 and 1 combinations is to use binary numbers.

If there are 3 ?'s then the combinations of 0's and 1's will be all binary numbers from 0 to 2^3 - 1:

0:  000
1:  001
2:  010
3:  011
4:  100
5:  101
6:  110
7:  111

So all you need to do is count the number of question mark characters (N) and then count from 0 to 2^N - 1 to generate all the possible 0 and 1 combinations.

Also I notice that half of these strings will have a 0 in the first position, and half will have a 1. I wonder if this feature could be used to reduce the amount of iteration you need to do.


Your code certainly looks like it works, and the use of recursion is 'OK'. What I don't like is that you repeat blocks of code in a way that makes the maintenance a problem.

There are some style nit-picks, but on the whole your code reads well. The indentation is a nice and consistent, the variable names are meaningful, and you are using braces for 1-liner conditionals. In other words, it is mostly great.

There are some problems:

  • I prefer a space between ){ parentheses. This is really minor though.
  • Your if/else blocks have unconventinal indentation:

            if (c == '?'){
                ... do stuff
                ... do stuff

    would normally be written:

        if (c == '?') {
            ... do stuff
        }  else {
            ... do stuff
  • the replaceHelper method should be private.

  • the result List should be declared as List<String> and not ArrayList<String>.

The algorithm you use is OK, start at the end, and work backwards, add 'stubs' to a List, and combine them as needed as you come back up the stack.

I don't like the sheer number of ArrayLists your create. Also, you are doing a lot of String concatenation.

Your algorithm would be a lot better if you:

  • passed a result array down the stack.
  • worked on a simple char[] array for the input.
  • used a more logical recursive structure of:
    1. check condition,
    2. do work & recursion
    3. return

By way of example, here's how I would do it:

public List<String> replaceAlt(String target) {
    final char[] chars = target.toCharArray();
    final List<String> result = new ArrayList<>();
    replaceHelperAlt(chars, 0, result);
    return result;

private void replaceHelperAlt(final char[] chars, final int i, final List<String> result) {
    if (i >= chars.length) {
        // searched the whole String, add the result.
        result.add(new String(chars));
    } else {
        if (chars[i] == '?') {

            // switch to 0, go deeper 
            chars[i] = '0';
            replaceHelperAlt(chars, i + 1, result);

            // switch to 1, go deeper 
            chars[i] = '1';
            replaceHelperAlt(chars, i + 1, result);

            // restore the ? on the return.
            chars[i] = '?';

        } else {

            // nothing to do, just go deeper.
            replaceHelperAlt(chars, i + 1, result);


The above solution has the benefits of:

  1. no unnecessary List instances and String instances are created (the only strings created are actual result values)
  2. the recursion is clearly located, and the end-condition of the stack is first.
  3. the simple char[] structure on the stack is very efficient.

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]) {
 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();
     int p = 0;
     for (Integer k : index) {
          sb.replace(k, k+1, "" + i.charAt(p));

Out put:

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

You can try this with any kind of a?b?c?d?e?e?...?z

  • 3
    \$\begingroup\$ This answer, given on Stack Ovrflow, and migrated here, is not a great Code Review answer. That's OK, but it's not a great alternative for the original problem either. The original code is neater, and more understandable. I am not sure that this is an improvement. \$\endgroup\$
    – rolfl
    Commented Aug 18, 2014 at 13:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.