Interview Question
package textSol;
import java.util.ArrayList;
import java.util.List;
import java.util.Vector;
public class textSol {
private List<String> sol;
private String input;
public textSol(String i)
{
input = i;
Vector <String> v = new Vector<>();
sol = new ArrayList<>();
for (int j = 0; j < input.length(); j++) {
if(input.charAt(j) == '?')
{
if(v.size() == 0)
{
v.add(cutString(input, j, '0'));
v.add(cutString(input, j, '1'));
}
else
{
int length = v.size();
for (int z = 0; z <length; z++) {
String s = v.get(0);
v.remove(0);
v.add(cutString(s, j, '0'));
v.add(cutString(s, j, '1'));
}
}
}
}
for (int t = 0; t < v.size(); t++) {
sol.add(v.get(t));
}
}
public List<String> getSol(){
return sol;
}
private String cutString(String s, int index,char fillChar)
{
if(index < s.length()-1)
{
return s.substring(0, index) + fillChar + s.substring(index+1);
}
else
{
return s.substring(0, index) + fillChar ;
}
}
public static void main(String[] args) {
textSol s = new textSol(args[0]);
List<String> sol = s.getSol();
for (String string : sol) {
System.out.println(string);
}
}
}
Recently found that Prof Skiena has a nice Java Class for any backtracking problem. Here is my attempt at doing this: All of you have to do overwrite a few methods and you are good with any backtracking problem.. For more info on this, check youtube "skiena backtracking"
class BackTracking {
static boolean finished = false;
static final int MAXCANDIDATES = 100;
static final int NMAX = 100;
static void backtrack(char a[], int k, int input) {
char c[] = new char[MAXCANDIDATES];
int ncandidates, i;
if (is_a_solution(a, k, input))
process_solution(a, k, input);
else {
k++;
ncandidates = construct_candidates(a, k, input, c);
for (i = 0; i < ncandidates; i++) {
a[k] = c[i];
make_move(a, k, input);
backtrack(a, k, input);
if (finished)
return;
unmake_move(a, k, input);
}
if(ncandidates > 1) a[k] = '?';
}
}
static void make_move(char a[], int k, int n) {
}
static void unmake_move(char a[], int k, int n) {
}
static void process_solution(char a[], int k, int n) {
System.out.println(new String(a));
}
static boolean is_a_solution(char a[], int k, int n) {
return k == n;
}
static int construct_candidates(char a[], int k, int n, char c[]) {
if(a[k] == '?') {
c[0] = '0';
c[1] = '1';
return 2;
}
c[0] = a[k];
return 1;
}
static public void main(String[] args) {
char a[] = "0?1?".toCharArray();
backtrack(a, 0, a.length-1);
}
}
Ok for design purists, this class can be declared abstract and all methods can be designed as generic but more starters, this is good enough..
I'm sure my solution could be optimized but the basic idea seems to me like this:
class Program
{
static List<string> result = new List<string>();
static int steps;
static List<int> positions = new List<int>();
static char[] inputchar = { '0', '?', '1', '?' };
static void Main(string[] args)
{
int j = 0;
for (int i = 0; i < inputchar.Length;i++ )
if (inputchar[i]=='?')
{
positions.Add(i);
steps++;
}
char[] tempchar = replaceWildCard(inputchar, (int)Math.Pow(2,steps)-1);
foreach (string item in result)
{
Console.WriteLine(item);
}
Console.ReadLine();
}
static char[] replaceWildCard(char[] input, int i)
{
if (i == -1) return input;
string bin = Convert.ToString(i, 2).PadLeft(positions.Count(), '0');
for (int j = 0; j < positions.Count(); j++) input[positions[j]] = bin[j];
result.Add(new string(input));
return replaceWildCard(inputchar, i - 1);
}
}
Output is:
0111
0110
0011
0010
Also tested this code with more input chars. Works fine.
If it has to be recursive one simple idea seems to be to split input into already visited part (xs) and part to be visited (ys). The solution is in Scala but can be easily adopted to Java:
def replaceWildcards(s: String) : List[String] = {
def replaceRecursive(xs: String, ys: String) : List[String] = {
if (ys.isEmpty()) List(xs)
else ys(0) match {
case '?' => replaceRecursive(xs+'0', ys.drop(1)) ::: replaceRecursive(xs+'1', ys.drop(1))
case a:Char => replaceRecursive(xs + a, ys.drop(1))
}
}
replaceRecursive("", s)
}
public static void fill(String input, int position) {
int nextposition = input.indexOf('?', position);
if(nextposition == -1) {
System.out.println(input);
return;
}
String input1 = input.substring(0, nextposition) + "0" + input.substring(nextposition+1, input.length());
fill(input1, nextposition+1);
String input2 = input1.substring(0, nextposition) + "1" + input1.substring(nextposition+1, input1.length());
fill(input2, nextposition+1);
}public static void main(String[] args) {
// TODO Auto-generated method stub
fill("?0?1",0);
}
def replaceWildcards(string: String) : Set[String] = {
if(!string.contains("?")) Set(string)
else replaceWildcards(string.replaceFirst("\\?", "0")) ++ replaceWildcards(string.replaceFirst("\\?", "1"))
}
//using the example, the inputs should be
// input == the input string
// alphabet = char[]{ '0', '1' }
public static ArrayList<String> getPerms(String input, char[] alphabet){
Worker worker = new Worker(input, alphabet){
worker.execute();
return worker.getResults();
}
static class Worker{
char[] origChars;
char[] working;
char[] alphabet;
ArrayList<String> results;
Worker(String origString, char[] alphabet){
this.origChars = origString.getCharArray();
this.alphabet = alphabet;
this.working = new char[this.origChars.length];
this.results = new ArrayList<String>();
}
void execute(){
this.execute(0);
}
void execute(int index){
if(index == this.working.length){
this.results.add(new String(this.working));
return;
}
if(this.origChars == '?'){
int nextIndex = index + 1;
for(char c : this.alphabet){
this.working[index] = c;
this.execute(nextIndex);
}
}
else{
this.working[index] = this.origChars[index];
this.execute(nextIndex+1);
}
}
ArrayList<String> getResults(){
return this.results;
}
}
public static void main(String[] args)
{
String s1 = "AB=C=";
printCombs(s1.indexOf('='), s1);
}
public static void printCombs(int start, String str)
{
if (start == -1)
{
System.out.println(str);
return;
}
String str1 = str.replaceFirst("=", "0");
printCombs(str1.indexOf('='), str1);
String str2 = str.replaceFirst("=", "1");
printCombs(str2.indexOf('='), str2);
}
This was somehow more difficult than I expected and the recursion I came up with isn't very clean, but I think I managed to get it correct
def replaceWildcards(s):
if len(s) == 1:
return [s[0]] if s[0] != "?" else ["0", "1"]
res = replaceWildcards(s[1:])
if s[0] == "?":
return map(lambda x: "0" + x, res) + map(lambda x: "1" + x, res)
return map(lambda x: s[0] + x, res)
import java.util.*;
public class main {
public static ArrayList<String> permutations=new ArrayList<String>();
public static void main(String[] args) {
System.out.println("Enter binary number with wildcard ?, print all permutations, ie 101? ");
Scanner numString=new Scanner(System.in)
String binaryNum=numString.nextLine();
getPermutations(binaryNum,0);
for(String num:permutations)
System.out.println("Permutation: "+num);
}
private static void getPermutations(String binaryNum, int index) {
if(index==binaryNum.length()){
permutations.add(binaryNum);
}
else {
if(binaryNum.charAt(index)!='?')
getPermutations(binaryNum, index+1);
else{
String string1=binaryNum.substring(0, index)+'0'+binaryNum.substring(index+1);
getPermutations(string1, index+1);
String string2=binaryNum.substring(0, index)+'1'+binaryNum.substring(index+1);
getPermutations(string2, index+1);
}
}
}
public static void replaceWildCardWithZeroOrOne(String input, int start) {
for (int index = start; index < input.length(); index++) {
if (input.charAt(index) == '?') {
final String firstSub = input.substring(0, index);
final String secondSub = input.substring(index + 1, input.length());
replaceWildCardWithZeroOrOne(firstSub + "0" + secondSub, index + 1);
replaceWildCardWithZeroOrOne(firstSub + "1" + secondSub, index + 1);
return;
}
}
System.out.println(input);
}
c# version
private static void WildCardsCombo(char[] str, int i, ref List<string> list)
{
string s = "";
while (i < str.Count() && str[i] != '?')
{
i++;
}
if (i == str.Count())
{
foreach (char c in str)
s += string.Concat(c.ToString());
list.Add(s);
Console.WriteLine("{0}", s);
return; //list;
}
if (str[i] == '?')
{
str[i] = '0';
WildCardsCombo(str, i, ref list);
str[i] = '1';
WildCardsCombo(str, i, ref list);
str[i] = '?';
}
return;
}
private List<String> list = new ArrayList<String>();
private void replaceAllWildCharacters(String str, int i) {
if (!str.contains("?")) {
list.add(str);
} else {
StringBuilder sb = new StringBuilder(str);
for (; i <= str.indexOf('?'); i++) {
if (str.charAt(i) == '?') {
char[] possibilities = new char[]{'0', '1'};
for (char ch : possibilities) {
sb.setCharAt(i, ch);
replaceAllWildCharacters(sb.toString(), i + 1);
}
}
}
}
}
public void stringCheck(char[] val,int i,int n) {
if (i == n) {
System.out.println(val);
} else if (val[i] == '?') {
val[i] = '1';
stringCheck(val, i + 1, n);
val[i] = '0';
stringCheck(val, i + 1, n);
val[i] = '?';
} else {
stringCheck(val, i + 1, n);
}
}
publlic void print() {
Scanner scan = new Scanner(System.in);
String s = scan.next();
stringCheck(s.toCharArray(),0,s.length);
}
/** js /
var str = '010?111?010011?011?1010?';
function loop_through_str(arg_str){
if(arg_str.indexOf('?') !== -1){
var new_str_1 = arg_str.replace('?', '1'),
new_str_0 = arg_str.replace('?', '0');
loop_through_str(new_str_0);
loop_through_str(new_str_1);
}else{
console.log(arg_str);
}
}
loop_through_str(str);
- Amit Dey December 22, 2014