## Wednesday, June 15, 2016

### Generate all binary strings from given pattern - GeeksforGeeks

Generate all binary strings from given pattern - GeeksforGeeks
Given a string containing of '0', '1' and '?' wildcard characters, generate all binary strings that can be formed by replacing each wildcard character by '0' or '1'.

```Input str = "1??0?101"
Output:
10000101
10001101
10100101
10101101
11000101
11001101
11100101
11101101
```
We pass index of next character to the recursive function. If the current character is a wildcard character ‘?’, we replace it by ‘0’ or ‘1’ and recurse for remaining characters. We print the string if we reaches its end.
`void` `print(string str, ``int` `index)`
`{`
`    ``if` `(index == str.size())`
`    ``{`
`        ``cout << str << endl;`
`        ``return``;`
`    ``}`

`    ``if` `(str[index] == ``'?'``)`
`    ``{`
`        ``// replace '?' by '0' and recurse`
`        ``str[index] = ``'0'``;`
`        ``print(str, index + 1);`

`        ``// replace '?' by '1' and recurse`
`        ``str[index] = ``'1'``;`
`        ``print(str, index + 1);`

`        ``// No need to backtrack as string is passed`
`        ``// by value to the function`
`    ``}`
`    ``else`
`        ``print(str, index + 1);`
`}`

`// Iterative function to generate all binary strings`
`// formed by replacing each wildcard character by 0`
`// or 1`
`void` `print(string str)`
`{`
`    ``queue<string> q;`
`    ``q.push(str);`

`    ``while` `(!q.empty())`
`    ``{`
`        ``string str = q.front();`

`        ``// find position of first occurrence of wildcard`
`        ``size_t` `index = str.find(``'?'``);`

`        ``// If no matches were found,`
`        ``// find returns string::npos`
`        ``if``(index != string::npos)`
`        ``{`
`            ``// replace '?' by '0' and push string into queue`
`            ``str[index] = ``'0'``;`
`            ``q.push(str);`

`            ``// replace '?' by '1' and push string into queue`
`            ``str[index] = ``'1'``;`
`            ``q.push(str);`
`        ``}`

`        ``else`
`            ``// If no wildcard characters are left,`
`            ``// print the string.`
`            ``cout << str << endl;`

`        ``q.pop();`
`    ``}`
`}`