Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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

Example: 
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 == '?'){
                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);
        }
    }
}
share|improve this question

migrated from stackoverflow.com Aug 18 at 13:28

This question came from our site for professional and enthusiast programmers.

    
What is happening?. Do you have a problem in the code? . –  TheLostMind Aug 18 at 11:46
1  
If your code is working, this would do better over at codereview.SE. –  Quirliom Aug 18 at 11:47
    
See binary numbers in output, you will find alternative approach –  Adi Aug 18 at 11:51
    
Assuming this is homework, this can be done more compact and lacks self-explanatory names (helper, preres). Also consider an empty string as input. –  Joop Eggen Aug 18 at 12:00
1  
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. –  Hot Licks Aug 18 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.

share|improve this answer

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
            }
            else{
                ... 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.
share|improve this answer

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);

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

share|improve this answer
2  
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. –  rolfl Aug 18 at 13:36

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.