Algorithm[recursive backtracking]: Generate all possible strings by replacing ? with 0 and 1


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.


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));
}


Labels

adsense (5) Algorithm (69) Algorithm Series (35) Android (7) ANT (6) bat (8) Big Data (7) Blogger (14) Bugs (6) Cache (5) Chrome (19) Code Example (29) Code Quality (7) Coding Skills (5) Database (7) Debug (16) Design (5) Dev Tips (63) Eclipse (32) Git (5) Google (33) Guava (7) How to (9) Http Client (8) IDE (7) Interview (88) J2EE (13) J2SE (49) Java (186) JavaScript (27) JSON (7) Learning code (9) Lesson Learned (6) Linux (26) Lucene-Solr (112) Mac (10) Maven (8) Network (9) Nutch2 (18) Performance (9) PowerShell (11) Problem Solving (11) Programmer Skills (6) regex (5) Scala (6) Security (9) Soft Skills (38) Spring (22) System Design (11) Testing (7) Text Mining (14) Tips (17) Tools (24) Troubleshooting (29) UIMA (9) Web Development (19) Windows (21) xml (5)