The original question from
http://www.codebytes.in/2014/11/coding-interview-question-given-string.html
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.
http://www.codebytes.in/2014/11/coding-interview-question-given-string.html
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.
public static List<String> replaceBy0Or1(String src) {
// store the ? positions
Objects.requireNonNull(src, "scr can'tt be null");
List<Integer> replaceIndex = new ArrayList<>();
for (int i = 0; i < src.length(); i++) {
if (src.charAt(i) == '?') {
replaceIndex.add(i);
}
}
StringBuilder sb = new StringBuilder(src);
List<String> result = new ArrayList<>();
helper(sb, replaceIndex, 0, result);
return result;
}
public static void helper(StringBuilder sb, List<Integer> replaceIndex,
int idx, List<String> result) {
if (idx == replaceIndex.size()) {
result.add(sb.toString());
return;
}
sb.setCharAt(replaceIndex.get(idx), '0');
helper(sb, replaceIndex, idx + 1, result);
sb.setCharAt(replaceIndex.get(idx), '1');
helper(sb, replaceIndex, idx + 1, result);
}
public static void main(String[] args) {
replaceBy0Or1("?c?o?d?e??").stream().forEach(
str -> System.out.println(str));
replaceBy0Or1("???").stream().forEach(str -> System.out.println(str));
replaceBy0Or1("?").stream().forEach(str -> System.out.println(str));
replaceBy0Or1("a").stream().forEach(str -> System.out.println(str));
replaceBy0Or1("").stream().forEach(str -> System.out.println(str));
}