Thursday, November 20, 2014

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

Question: 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.

Algorithm:
1. Count the number of '?'s in the string.
2. Initialize a char [] of that size.
3. Insert the possible sequences of 0s and 1s in the array.
4. Everytime when the array is filled, replace ?s in the string with the contents of the filled array.

Source:

public class Code{ 
    public static void print(String s, char[] a){ 
        System.out.println();
        
        int j = 0;
        for(int i=0;i<s.length();++i)
            if(s.charAt(i)=='?')System.out.print(a[j++]);
            else System.out.print(s.charAt(i)); 
    }
    
    public static void process(String string, char[] a, int len, int cIndex){
        if(cIndex == len) {print(string, a); return;} 
    
        a[cIndex] = '0';
        process(string, a, len, cIndex+1);
        a[cIndex] = '1';
        process(string, a, len, cIndex+1);
    }
    
    public static void input(String string){
        int l = 0;
        for(int i = 0;i<string.length(); ++i)
            if(string.charAt(i)=='?') l++;
        char a[] = new char[l]; 
        process(string, a, l, 0);
    }
    
    public static void main(String[] args){
        String s = "?c?o?d?e??";
        input(s); 
        s = "???";
        input(s);
    }
}

Output:

000
001
010
011
100
101
110
111

0c0o0d0e00
0c0o0d0e01
0c0o0d0e10
0c0o0d0e11
0c0o0d1e00
0c0o0d1e01
0c0o0d1e10
0c0o0d1e11
0c0o1d0e00
0c0o1d0e01
0c0o1d0e10
0c0o1d0e11
0c0o1d1e00
0c0o1d1e01
0c0o1d1e10
0c0o1d1e11
0c1o0d0e00
0c1o0d0e01
0c1o0d0e10
0c1o0d0e11
0c1o0d1e00
0c1o0d1e01
0c1o0d1e10
0c1o0d1e11
0c1o1d0e00
0c1o1d0e01
0c1o1d0e10
0c1o1d0e11
0c1o1d1e00
0c1o1d1e01
0c1o1d1e10
0c1o1d1e11
1c0o0d0e00
1c0o0d0e01
1c0o0d0e10
1c0o0d0e11
1c0o0d1e00
1c0o0d1e01
1c0o0d1e10
1c0o0d1e11
1c0o1d0e00
1c0o1d0e01
1c0o1d0e10
1c0o1d0e11
1c0o1d1e00
1c0o1d1e01
1c0o1d1e10
1c0o1d1e11
1c1o0d0e00
1c1o0d0e01
1c1o0d0e10
1c1o0d0e11
1c1o0d1e00
1c1o0d1e01
1c1o0d1e10
1c1o0d1e11
1c1o1d0e00
1c1o1d0e01
1c1o1d0e10
1c1o1d0e11
1c1o1d1e00
1c1o1d1e01
1c1o1d1e10
1c1o1d1e11

No comments:

Post a Comment