# Replacing the occurence of the character in string

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 == '?'){
}
else{
}
return res;
}
ArrayList<String> res = new ArrayList<String>();
ArrayList<String> preRes = replaceHelper(target, to-1);
if (c == '?'){
for (String token: preRes){
}
}
else{
for (String token: preRes){
}
}
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);
}
}
}

-

## migrated from stackoverflow.comAug 18 '14 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 '14 at 11:46
If your code is working, this would do better over at codereview.SE. –  Quirliom Aug 18 '14 at 11:47
See binary numbers in output, you will find alternative approach –  Adi Aug 18 '14 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 '14 at 12:00
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 '14 at 12:06

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
}
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.
} 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]) {
occurrence++;
}
}
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++;
}

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

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