Google Interview Question
Software EngineersCountry: United States
Too much of scan like contains , replaceFirst. How about this.
public class PatternProduce {
public static void produce(char[] in, int index, String output) {
if(index == in.length) {
System.out.println(" " + output);
return;
}
if(in[index] == '?') {
produce(in, index+1, output+"0");
produce(in, index+1, output+"1");
} else {
produce(in, index+1, output+in[index]);
}
}
public static void main(String[] args) {
String in = "10?";
produce(in.toCharArray(), 0, new String());
in = "01?0?";
produce(in.toCharArray(), 0, new String());
}
}
import java.util.Arrays;
public class WildCardsFor1Or0 {
public static void main(String[] args) {
int n=0;
String value="?1?1??";
String[] s=value.split("\\?+");
String input="";
for(int i=0;i<value.length();i++){
if(value.charAt(i)=='?'){
input+="0";
}
}
double Qcount=Math.pow(2,input.length());
System.out.println(value.replace("?", "0"));
StringBuffer temp=new StringBuffer(input);
for(int j=0;j<Qcount-1;j++){
for(int i=temp.length()-1;i>=0;i--){
if(temp.charAt(i)=='0'){
if(i==temp.length()){
temp.setCharAt(i, '1');
break;
}
else{
temp.setCharAt(i, '1');
int len=temp.length()-i;
for(int k=i+1;k<temp.length();k++){
temp.setCharAt(k, '0');
}
break;
}
}
}
String output="";
int innercount=0;
int innercount1=0;
for(int i=0;i<value.length();i++){
if(value.charAt(i)=='?'){
output+=temp.charAt(innercount);
innercount++;
}
else{
output+=value.charAt(i);
}
}
System.out.println(output);
}
}
}
import java.util.Arrays;
public class WildCardsFor1Or0 {
public static void main(String[] args) {
int n=0;
String value="?1?1??";
String[] s=value.split("\\?+");
String input="";
for(int i=0;i<value.length();i++){
if(value.charAt(i)=='?'){
input+="0";
}
}
double Qcount=Math.pow(2,input.length());
System.out.println(value.replace("?", "0"));
StringBuffer temp=new StringBuffer(input);
for(int j=0;j<Qcount-1;j++){
for(int i=temp.length()-1;i>=0;i--){
if(temp.charAt(i)=='0'){
if(i==temp.length()){
temp.setCharAt(i, '1');
break;
}
else{
temp.setCharAt(i, '1');
int len=temp.length()-i;
for(int k=i+1;k<temp.length();k++){
temp.setCharAt(k, '0');
}
break;
}
}
}
String output="";
int innercount=0;
int innercount1=0;
for(int i=0;i<value.length();i++){
if(value.charAt(i)=='?'){
output+=temp.charAt(innercount);
innercount++;
}
else{
output+=value.charAt(i);
}
}
System.out.println(output);
}
}
}
import java.util.Arrays;
public class WildCardsFor1Or0 {
public static void main(String[] args) {
int n=0;
String value="?1?1??";
String[] s=value.split("\\?+");
String input="";
for(int i=0;i<value.length();i++){
if(value.charAt(i)=='?'){
input+="0";
}
}
double Qcount=Math.pow(2,input.length());
System.out.println(value.replace("?", "0"));
StringBuffer temp=new StringBuffer(input);
for(int j=0;j<Qcount-1;j++){
for(int i=temp.length()-1;i>=0;i--){
if(temp.charAt(i)=='0'){
if(i==temp.length()){
temp.setCharAt(i, '1');
break;
}
else{
temp.setCharAt(i, '1');
int len=temp.length()-i;
for(int k=i+1;k<temp.length();k++){
temp.setCharAt(k, '0');
}
break;
}
}
}
String output="";
int innercount=0;
int innercount1=0;
for(int i=0;i<value.length();i++){
if(value.charAt(i)=='?'){
output+=temp.charAt(innercount);
innercount++;
}
else{
output+=value.charAt(i);
}
}
System.out.println(output);
}
}
}
public static void getBitStrings(String s) {
listPossibilities(s, "", 0);
}
public static void listPossibilities(String bitString, String currentString, int currentIndex) {
int length = bitString.length();
if (currentIndex == length) {
System.out.println(currentString);
return;
}
if (bitString.charAt(currentIndex) == '?') {
listPossibilities(bitString, currentString + '0', currentIndex + 1);
listPossibilities(bitString, currentString + '1', currentIndex + 1);
return;
}
listPossibilities(bitString, currentString + bitString.charAt(currentIndex), currentIndex + 1);
}
had the same solution in C#
private static void wildcardReplace(string source, string currentSource, int startIndex, ref List<string> permutation)
{
if (startIndex == source.Length)
{
permutation.Add(currentSource);
return;
}
if ('?' == source[startIndex])
{
wildcardReplace(source, currentSource + '0', startIndex + 1, ref permutation);
wildcardReplace(source, currentSource + '1', startIndex + 1, ref permutation);
return;
}
wildcardReplace(source, currentSource + source[startIndex], startIndex + 1, ref permutation);
}
The wildcard positions have to be filled with all possible combination of 0 and 1. This can be done by backtracking but the best way is to check all numbers from 0 to 2^(total wildcard) - 1 and set 0 or 1 by checking its bit pattern.
Complexity is O(2^n) in worst case.
vector<string> wildcardFillUp(string bitStream) {
vector<string> result;
vector<int> positions;
int cnt = 0;
int len = bitStream.length();
for(int i = 0; i < len; ++i) {
if(bitStream[i] == '?') {
positions.push_back(i);
++cnt;
}
}
int n = (1 << cnt) - 1;
for(int i = 0; i <= n; ++i) {
for(int idx = 0, k = cnt - 1; k >= 0; --k) {
bool isSet = (bool) (i & (1 << k));
bitStream[positions[idx++]] = isSet ? '1' : '0';
}
result.push_back(bitStream);
}
return result;
}
#include <iostream>
#include <string>
#include <vector>
using namespace std;
vector<string> produce(string p) {
vector<string> res;
if (p.empty()) return res;
vector<int> wildcards;
for (int i = 0; i != p.size(); ++i)
if (p[i] == '?')
wildcards.push_back(i);
for (int i = 0; i != (1 << wildcards.size()); ++i) {
string r(p);
for (int j = 0; j != wildcards.size(); ++j) {
r[wildcards[j]] = (i & (1 << j)) ? '1' : '0';
}
res.push_back(r);
}
return res;
}
int main() {
string p;
cout << "Enter pattern: ";
getline (cin, p);
vector<string> res = produce(p);
for (int i = 0; i != res.size(); ++i) {
cout << res[i] << endl;
}
}
/* modified find combination code.
concept: backtracking
call printCombination("01?1?0", new StringBuffer(),0);
*/
public static void printCombination(String str, StringBuffer buff, int index){
if(index==str.length()){
System.out.println(buff.toString());
return;
}else if(index > str.length()){
return;
}
if(str.charAt(index)=='?'){
buff.append('0');
printCombination(str,buff, index+1);
buff.setLength(buff.length()-1);
buff.append('1');
printCombination(str,buff, index+1);
buff.setLength(buff.length()-1);
}else{
buff.append(str.charAt(index));
printCombination(str,buff, index+1);
buff.setLength(buff.length()-1);
}
}
int main() {
string s = "01?0?";
vector<string> results;
vector<int> indexes;
results.push_back(s);
for (int i = 0; i < s.size(); i++) {
if (s[i] == '?') {
indexes.push_back(i);
}
}
wild_char_fillup(results, indexes);
for (int i = 0; i < results.size(); i++) {
cout << results[i] << endl;
}
}
void wild_char_fillup(vector<string> &results, vector<int> &indexes) {
for (int i = 0; i < indexes.size(); i++) {
int size = results.size();
for (int j = 0; j < size; j++) {
string str = results[0];
results.erase(results.begin());
str = replace(str, indexes[i], '0');
results.push_back(str);
str = replace(str, indexes[i], '1');
results.push_back(str);
}
}
}
string replace(string str, int index, char c) {
str[index] = c;
return str;
}
def wildcard(wildcard_string):
list_of_strings = []
for c in wildcard_string:
if not list_of_strings:
if c == '?':
list_of_strings.append('0')
list_of_strings.append('1')
else:
list_of_strings.append(c)
else:
new_list_of_strings = []
for string in list_of_strings:
if c == '?':
new_list_of_strings.append(string + '0')
new_list_of_strings.append(string + '1')
else:
new_list_of_strings.append(string + c)
list_of_strings = new_list_of_strings
return list_of_strings
print wildcard('01?0?')
vector<string> wildcardMatch(string &s)
{
int n = s.size(); vector<int> indexs; vector<string> ans;
for (int i = 0; i < n; ++i) if (s[i] == '?') indexs.push_back(i);
n = indexs.size();
for (int mask = 0; mask < (1 << n); ++mask)
{
int tmp = mask;
for (int i = 0; i < n; ++i, tmp >>= 1) s[indexs[i]] = (tmp & 1) ? '1' : '0';
ans.push_back(s);
}
return move(ans);
}
static List<String> produceFromWildCard(String input) {
List<String> result = new LinkedList<String>();
produceFromWildCard(input, result);
return result;
}
static void produceFromWildCard(String input, List<String> result) {
int indexWild = input.indexOf('?');
if (indexWild < 0) {
result.add(input);
return;
}
produceFromWildCard(input.substring(0, indexWild) + "0"
+ input.substring(indexWild + 1), result);
produceFromWildCard(input.substring(0, indexWild) + "1"
+ input.substring(indexWild + 1), result);
}
public static void printPer(String s, int cursor) {
if(cursor >= s.length()) {
System.out.println(s);
return;
}
if(s.charAt(cursor) == '?') {
String s1 = s.substring( 0, cursor) + "1" + s.substring(cursor+1, s.length());
String s2 = s.substring( 0, cursor) + "0" + s.substring(cursor+1, s.length());
printPer(s1, cursor+1);
printPer(s2, cursor+1);
} else {
printPer(s, cursor+1);
}
}
public static void main(String[] args) {
Permutation.printPer("01?0?", 0);
}
#include <string>
#include <iostream>
using namespace std;
void expand(std::string prefix, std::string suffix)
{
if (suffix.length() == 0)
{
std::cout << prefix << std::endl;
return;
}
else if (suffix[0] != '?')
expand(prefix + suffix[0], suffix.substr(1));
else
{
expand(prefix + '1', suffix.substr(1));
expand(prefix + '0', suffix.substr(1));
}
}
int main() {
string s = "01?0?";
expand(string(""), s);
}
#include <string>
#include <iostream>
using namespace std;
void expand(std::string prefix, std::string suffix)
{
if (suffix.length() == 0)
{
std::cout << prefix << std::endl;
return;
}
else if (suffix[0] != '?')
expand(prefix + suffix[0], suffix.substr(1));
else
{
expand(prefix + '1', suffix.substr(1));
expand(prefix + '0', suffix.substr(1));
}
}
int main() {
string s = "01?0?";
expand(string(""), s);
}
public static List<string> GetBitString(string input)
{
var output = new List<string>();
var first = true;
foreach (var t in input)
{
if(first)
{
if (t == '?')
{
output.Add("1");
output.Add("0");
}
else
{
output.Add(t.ToString());
}
first = false;
continue;
}
if (t == '?')
{
var temp1 = new List<string>();
for (int i = 0; i < output.Count(); i++)
{
temp1.Add(output[i] + "1");
}
var temp2 = new List<string>();
for (int i = 0; i < output.Count(); i++)
{
temp2.Add(output[i] + "0");
}
output = temp1;
output.AddRange(temp2);
}
else
{
for (int i = 0; i < output.Count(); i++)
{
output[i] = output[i] + t;
}
}
}
return output;
}
public static List<string> GetBitString(string input)
{
var output = new List<string>();
var first = true;
foreach (var t in input)
{
if(first)
{
if (t == '?')
{
output.Add("1");
output.Add("0");
}
else
{
output.Add(t.ToString());
}
first = false;
continue;
}
if (t == '?')
{
var temp1 = new List<string>();
for (int i = 0; i < output.Count(); i++)
{
temp1.Add(output[i] + "1");
}
var temp2 = new List<string>();
for (int i = 0; i < output.Count(); i++)
{
temp2.Add(output[i] + "0");
}
output = temp1;
output.AddRange(temp2);
}
else
{
for (int i = 0; i < output.Count(); i++)
{
output[i] = output[i] + t;
}
}
}
return output;
}
#include <cstdlib>
using namespace std;
#include <stdio.h>
#include <string.h>
void print_wildcard(char *s, int i)
{
if(s[i] == 0)
{
printf("%s\n", s);
return;
}
if(s[i] == '?')
{
s[i] = '0';
print_wildcard(s,i+1);
s[i] = '1';
print_wildcard(s,i+1);
s[i] = '?';
}
else
{
print_wildcard(s,i+1);
}
}
void print_wildcard(char *in)
{
char *temp = new char [strlen(in)+1];
strcpy(temp,in);
print_wildcard(temp,0);
delete[] temp;
}
int main(int argc, char** argv) {
print_wildcard("01?0?");
return 0;
}
def _helper(result, s, word, i, l):
if i == l:
result.append(word)
return
if s[i] == "0" or s[i] == "1":
_helper(result, s, word+s[i], i+1, l)
else:
_helper(result, s, word+"0", i+1, l)
_helper(result, s, word+"1", i+1, l)
return result
def expand(expression):
return _helper([], expression, "", 0, len(expression))
import java.util.ArrayList;
import java.util.List;
public class WildCardResolver {
public static List<String> resolveWildCardString(String input) {
int startFrom = 0;
int wildCardSize = 0;
List<Integer> wildCardIndexes = new ArrayList<Integer>();
List<String> output = new ArrayList<String>();
int currentIndex = -1;
while ((currentIndex = input.indexOf("?", startFrom)) != -1) {
++ wildCardSize;
wildCardIndexes.add(currentIndex);
startFrom = currentIndex + 1;
}
if (wildCardSize == 0) {
output.add(input);
return output;
}
List<String> result = new ArrayList<String>();
String temp = "";
getAllPermutations("01", wildCardSize, temp, output);
for (int i = 0; i < output.size(); ++i) {
char[] inputChars = input.toCharArray();
String possibleOutputItem = output.get(i);
char[] possibleOIChars = possibleOutputItem.toCharArray();
int possibleOICharsIndex = 0;
for (int j = 0; j < wildCardIndexes.size(); ++j) {
inputChars[wildCardIndexes.get(j)] = possibleOIChars[possibleOICharsIndex ++];
}
result.add(new String(inputChars));
}
return result;
}
public static void getAllPermutations(String input, int size, String temp, List<String> output) {
if (temp.length() >= size) {
output.add(temp);
} else {
for (int i = 0; i < input.length(); ++i) {
String newTemp = temp + input.charAt(i);
getAllPermutations(input, size, newTemp, output);
}
}
}
public static void main(String[] args) {
List<String> output = resolveWildCardString("01?0?");
for (String item : output) {
System.out.println(item);
}
}
}
here is a simple solution
void printPattern(const string& s, string& buf, int i){
if (i >= s.size()){
cout << buf << endl;
return;
}
if (s[i] == '?' ){
for (int k = 0; k <= 1; k++){
buf[i] = '0' + k;
printPattern(s, buf, i + 1);
}
}
else{
buf[i] = s[i];
printPattern(s, buf, i + 1);
}
}
void printPattern(const string& s){
string buf;
buf.resize(s.size());
printPattern(s, buf, 0);
}
In C:
#include <stdio.h>
#include <string.h>
void wildcard(char *s, int idx)
{
int i;
for (i=idx; i < strlen(s); i++)
{
if (s[i] == '?')
{
s[i] = '0';
wildcard(s, i+1);
s[i] = '1';
wildcard(s,i+1);
s[i]='?';
return;
}
}
printf("\n-->%s", s);
}
int main()
{
char s[] = "01?0?";
printf("\n Input string: %s", s);
wildcard(s,0);
getchar();
return 1;
}
In C:
#include <stdio.h>
#include <string.h>
void wildcard(char *s, int idx)
{
int i;
for (i=idx; i < strlen(s); i++)
{
if (s[i] == '?')
{
s[i] = '0';
wildcard(s, i+1);
s[i] = '1';
wildcard(s,i+1);
s[i]='?';
return;
}
}
printf("\n-->%s", s);
}
int main()
{
char s[] = "01?0?";
printf("\n Input string: %s", s);
wildcard(s,0);
getchar();
return 1;
}
In C:
#include <stdio.h>
#include <string.h>
void wildcard(char *s, int idx)
{
int i;
for (i=idx; i < strlen(s); i++)
{
if (s[i] == '?')
{
s[i] = '0';
wildcard(s, i+1);
s[i] = '1';
wildcard(s,i+1);
s[i]='?';
return;
}
}
printf("\n-->%s", s);
}
int main()
{
char s[] = "01?0?";
printf("\n Input string: %s", s);
wildcard(s,0);
getchar();
return 1;
}
Has the benefit of not creating extra interim objects at every level in the function call stack. Runtime: O(n^2), memory O(n) of which is only consumed by the function call stack and only for each '?'.
public static void getPerms(String str){
if(str == null){
throw new NullPointerException();
}
Worker worker = new Worker(str);
worker.work();
}
public static class Worker{
private char[] arr;
private StringBuilder line;
private int index;
public Worker(String str){
this.arr = str.toCharArray();
this.line = new StringBuilder();
this.index = 0;
}
public void work(){
while(this.index < this.arr.length){
if(this.arr[this.index] == '?'){
this.arr[this.index] = '0';
this.index++;
this.work();
this.arr[this.index -1] = '1';
this.work();
this.index--;
this.arr[this.index] = '?';
return;
}
this.index++;
}
this.print();
}
private void print(){
this.line.setLength(0);
for(int i = 0; i < this.arr.length; i++){
line.append(this.arr[i]);
}
java.lang.System.out.println(line.toString());
}
}
#include<iostream>
#include<string>
using namespace std;
void printAll(int start,const string& st) {
static string ss;
if(start==0)
ss=st;
int l=ss.length();
int i=start;
while( (ss[i]!='?') && i<l)
i++;
if(i<l) {
ss[i]='0';
printAll(i+1,st);
ss[i]='1';
printAll(i+1,st);
ss[i]='?';
} else
cout<<ss<<endl;
}
int main() {
string str="01?0?";
printAll(0,str);
}
static void combine(String in) {
// TODO Auto-generated method stub
int index = in.indexOf('?');
if(index != -1)
{
System.out.println(in.substring(0, index) + "1" + in.substring(index+1));
System.out.println(in.substring(0, index) + "0" + in.substring(index+1));
combine(in.substring(0, index) + "0" + in.substring(index+1));
combine(in.substring(0, index) + "1" + in.substring(index+1));
} else {
return;
}
}
I solve this problem with an odometer approach, the number of '?' determine the length of the odometer, I use an array to manage/store the odometer. A StringBuilder is used to generate the resulting strings. To modify the StringBuilder I use a second array that store the indexes to modify (C# implementation)
public List<string> ParseWildcard(string s)
{
List<string> result = new List<string>();
List<int> indexes = new List<int>();
List<int> odometer = new List<int>();
StringBuilder sb = new StringBuilder();
for (int i = 0; i < s.Length; i++)
{
if (s[i] == '?')
{
indexes.Add(i);
odometer.Add(0);
sb.Append('0');
}
else
sb.Append(s[i]);
}
if (odometer.Count == 0)
{
result.Add(s);
return result;
}
bool lastChanged = false;
int lastIndex = odometer.Count - 1;
while (!lastChanged)
{
result.Add(sb.ToString());
int i = 0;
int j = i - 1;
while (i != j && i <= lastIndex)
{
j = i;
odometer[i] = (odometer[i] + 1) % 2;
if (odometer[i] == 0)
{
lastChanged = i == lastIndex;
i++;
}
sb[indexes[j]] = (char)(odometer[j] + 48);
}
}
return result;
}
// Test Code
//string s = "010010";
//string s = "01?";
string s = "01?0?";
var result = ParseWildcard(s);
foreach (var item in result)
Console.WriteLine(item);
import java.util.Arrays;
public class WildCardsFor1Or0 {
public static void main(String[] args) {
// TODO Auto-generated method stu
int n=0;
String value="?1?1??";
String[] s=value.split("\\?+");
//System.out.println(Arrays.toString(s));
String input="";
for(int i=0;i<value.length();i++){
if(value.charAt(i)=='?'){
input+="0";
}
}
double Qcount=Math.pow(2,input.length());
System.out.println(value.replace("?", "0"));
StringBuffer temp=new StringBuffer(input);
for(int j=0;j<Qcount-1;j++){
for(int i=temp.length()-1;i>=0;i--){
if(temp.charAt(i)=='0'){
if(i==temp.length()){
temp.setCharAt(i, '1');
break;
}
else{
temp.setCharAt(i, '1');
int len=temp.length()-i;
for(int k=i+1;k<temp.length();k++){
temp.setCharAt(k, '0');
}
break;
}
}
}
String output="";
int innercount=0;
int innercount1=0;
for(int i=0;i<value.length();i++){
if(value.charAt(i)=='?'){
output+=temp.charAt(innercount);
innercount++;
}
else{
output+=value.charAt(i);
}
}
System.out.println(output);
}
}
}
import java.util.Arrays;
public class WildCardsFor1Or0 {
public static void main(String[] args) {
// TODO Auto-generated method stu
int n=0;
String value="?1?1??";
String[] s=value.split("\\?+");
//System.out.println(Arrays.toString(s));
String input="";
for(int i=0;i<value.length();i++){
if(value.charAt(i)=='?'){
input+="0";
}
}
double Qcount=Math.pow(2,input.length());
System.out.println(value.replace("?", "0"));
StringBuffer temp=new StringBuffer(input);
for(int j=0;j<Qcount-1;j++){
for(int i=temp.length()-1;i>=0;i--){
if(temp.charAt(i)=='0'){
if(i==temp.length()){
temp.setCharAt(i, '1');
break;
}
else{
temp.setCharAt(i, '1');
int len=temp.length()-i;
for(int k=i+1;k<temp.length();k++){
temp.setCharAt(k, '0');
}
break;
}
}
}
String output="";
int innercount=0;
int innercount1=0;
for(int i=0;i<value.length();i++){
if(value.charAt(i)=='?'){
output+=temp.charAt(innercount);
innercount++;
}
else{
output+=value.charAt(i);
}
}
System.out.println(output);
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stu
int n=0;
String value="?1?1??";
String[] s=value.split("\\?+");
//System.out.println(Arrays.toString(s));
String input="";
for(int i=0;i<value.length();i++){
if(value.charAt(i)=='?'){
input+="0";
}
}
double Qcount=Math.pow(2,input.length());
System.out.println(value.replace("?", "0"));
StringBuffer temp=new StringBuffer(input);
for(int j=0;j<Qcount-1;j++){
for(int i=temp.length()-1;i>=0;i--){
if(temp.charAt(i)=='0'){
if(i==temp.length()){
temp.setCharAt(i, '1');
break;
}
else{
temp.setCharAt(i, '1');
int len=temp.length()-i;
for(int k=i+1;k<temp.length();k++){
temp.setCharAt(k, '0');
}
break;
}
}
}
String output="";
int innercount=0;
int innercount1=0;
for(int i=0;i<value.length();i++){
if(value.charAt(i)=='?'){
output+=temp.charAt(innercount);
innercount++;
}
else{
output+=value.charAt(i);
}
}
System.out.println(output);
}
}
{
int n=0;
String value="?1?1??";
String[] s=value.split("\\?+");
String input="";
for(int i=0;i<value.length();i++){
if(value.charAt(i)=='?'){
input+="0";
}
}
double Qcount=Math.pow(2,input.length());
System.out.println(value.replace("?", "0"));
StringBuffer temp=new StringBuffer(input);
for(int j=0;j<Qcount-1;j++){
for(int i=temp.length()-1;i>=0;i--){
if(temp.charAt(i)=='0'){
if(i==temp.length()){
temp.setCharAt(i, '1');
break;
}
else{
temp.setCharAt(i, '1');
int len=temp.length()-i;
for(int k=i+1;k<temp.length();k++){
temp.setCharAt(k, '0');
}
break;
}
}
}
String output="";
int innercount=0;
int innercount1=0;
for(int i=0;i<value.length();i++){
if(value.charAt(i)=='?'){
output+=temp.charAt(innercount);
innercount++;
}
else{
output+=value.charAt(i);
}
}
System.out.println(output);
}
}
import java.util.Arrays;
public class WildCardsFor1Or0 {
public static void main(String[] args) {
int n=0;
String value="?1?1??";
String[] s=value.split("\\?+");
String input="";
for(int i=0;i<value.length();i++){
if(value.charAt(i)=='?'){
input+="0";
}
}
double Qcount=Math.pow(2,input.length());
System.out.println(value.replace("?", "0"));
StringBuffer temp=new StringBuffer(input);
for(int j=0;j<Qcount-1;j++){
for(int i=temp.length()-1;i>=0;i--){
if(temp.charAt(i)=='0'){
if(i==temp.length()){
temp.setCharAt(i, '1');
break;
}
else{
temp.setCharAt(i, '1');
int len=temp.length()-i;
for(int k=i+1;k<temp.length();k++){
temp.setCharAt(k, '0');
}
break;
}
}
}
String output="";
int innercount=0;
int innercount1=0;
for(int i=0;i<value.length();i++){
if(value.charAt(i)=='?'){
output+=temp.charAt(innercount);
innercount++;
}
else{
output+=value.charAt(i);
}
}
System.out.println(output);
}
}
}
One more way
626 void print_wildcard(char *S, char *res, int i, int n) {
627
628 if(i>n){
629 /*res[i] = S[i];*/
630 printf("%s\n", res);
631 return;
632 }
633
634 if(S[i]!='?'){
635 res[i] = S[i];
636 print_wildcard(S, res, i+1, n);
637
638 }else {
639 S[i] = '0';
640 res[i] = S[i];
641 print_wildcard(S, res, i+1, n);
642 S[i] = '1';
643 res[i] = S[i];
644 print_wildcard(S, res, i+1, n);
645 S[i] = '?'; //move the string back to the origial character
646 }
647
}
function binary_wildcard($s){
$count = 0;
for($i=0; $i<strlen($s); $i++){
if($s[$i] == "?"){
$count++;
}
}
$combs = pow(2, $count);
for($i=0; $i<$combs; $i++){
$b = sprintf("%0" . $count . 'b', $i);
$j=0;
$k=0;
$tmp = $s;
for($j=0; $j<strlen($tmp); $j++){
if($tmp[$j] == "?"){
$tmp[$j] = $b[$k];
$k++;
}
}
echo $tmp . '<br/>';
}
}
- Chris May 09, 2015