строковые комбинации 0 и 1

Question

Мне задали этот вопрос в интервью:

Учитывая строку s, состоящую из 0, 1 и ?.Знак вопроса может быть либо 0, либо 1.Найти все возможные комбинации для строки.

Я придумал приведенный ниже код, но я хотел знать, является ли это наилучшим способом решения проблемы, а также меня смущает сложность времени?

  public static void main(String[] args) {
    List<String> output = new ArrayList<>();
    addCombinations("0?1?", 0, output);
    System.out.println(output);
  }

  private static void addCombinations(String input, int index, List<String> output) {
    for (int i = index; i < input.length(); ++i) {
      if (input.charAt(i) == '?') {
        addCombinations(input.substring(0, i) + "0" + input.substring(i + 1), i + 1, output);
        addCombinations(input.substring(0, i) + "1" + input.substring(i + 1), i + 1, output);
        return;
      }
    }
    output.add(input);
  }

Answer 1

Если количество знаков вопроса в данной строке равно m, возможное количество комбинаций равно 2 ^ m.Так почему?

Для "?"Ответ "0", "1"

Для "??"Ответ "00", "01", "1,0", "11" (добавление 0 и 1 с каждым результатом "?" = ("0", "1"))

For "???»Ответ: «000», «001», «010», «011», «100», «101», «110», «111», (суммируя 0 и 1 с каждым результатом «??»)

Когда количество знаков вопроса равно 1, возможное количество комбинаций равно 2 = 2 ^ 1.
Когда количество знаков вопроса равно 2, возможное количество комбинаций равно 2 * 2 = 4 = 2 ^ 2.
Когда количество знаков вопроса равно 3, возможное количество комбинаций равно 4 * 2 = 8 = 2 ^ 3.
Когда число знаков вопроса равно 4, возможное количество комбинаций равно 8 * 2 = 16= 2 ^ 4.
Когда количество знаков вопроса равно 5, возможное количество комбинаций равно 16 * 2 = 32 = 2 ^ 5.
Когда количество знаков вопроса равно 6, возможное количество комбинаций равно 32* 2 = 64 = 2 ^ 6.
Если число вопросов равно 7, возможное число комбинаций равно 64 * 2 = 128 = 2 ^ 7.

Таким образом, когда число вопросительных знаков равно m, возможное число комбинаций равно 2 ^ m.

Как мы знаем из двоичной системы, что каждое число от 0 до (2 ^ m) -1дает комбинацию двоичных 0 и 1.

Так что, когда длина равна 1, мы можем рассмотреть от 0 до (2 ^ 1) -1 = 1

0 0
1 1 

Так, когда длина равна2, мы можем рассмотреть от 0 до (2 ^ 2) -1 = 3

0 00
1 01
2 10
3 11

Таким образом, когда длина равна 3, мы можем рассмотреть от 0 до (2 ^ 3) -1 = 7

0 000
1 001
2 010
3 011
4 100
5 101
6 110
7 111

Аналогично для длины m мы можем рассмотреть 0 до (2 ^ m) -1.

Таким образом, мы можем взять каждое число от 0 до (2 ^ m) -1.

Для каждого числа мы будем проверять каждый бит от 0 до m-1.
Если i-й бит равен 0, мы будем ставить 0 в i-й '?'.
Если i-йбит равен 1, мы поместим 1 в i-й '?'.

Таким образом, мы получим 2 ^ m различных строк.

Answer 2

Трудно сказать, что лучше или нет. Если это работает, понятно и не имеет очень плохой производительности, тогда, вероятно, все в порядке.

Вот простой, который я написал, который использует некоторую бухгалтерию для отслеживания позиций, которые будут заполнены.

   public static void main(String[] args) {
      List<String> bitStrings = generate("0?1?0?11");
      bitStrings.forEach(System.out::println);
   }

   public static List<String> generate(String pattern) {
      List<String> output = new ArrayList<>();

      //Starting bit template
      String start = pattern.replaceAll("\\?", "0");

      //get the changeable positions.
      int[] pos = IntStream.range(0, pattern.length()).filter(
            i -> pattern.charAt(i) == '?').toArray();

      // Now simply iterate thru the 2^n possibilities where
      // n is the number of changeable positions.
      for (int i = 0; i < 1 << pos.length; i++) {
         StringBuilder sb = new StringBuilder(start);
         int p = i;
         for (int k = 0; k < pos.length; k++) {
            sb.setCharAt(pos[k], (char) ((p & 1) + '0'));
            p >>= 1;
         }
         output.add(sb.toString());
      }
      return output;
   }

Answer 3

Вот другая реализация, которая не использует рекурсию и не использует конкатенацию строк.

private static List<String> addCombinations(String input) {
    char[] chars = input.toCharArray();
    List<Integer> wildcardIndex = new ArrayList<>();
    for (int i = 0; i < chars.length; i++) {
        if (chars[i] == '?') {
            wildcardIndex.add(i);
            chars[i] = '0';
        }
    }
    if (wildcardIndex.size() > 31)
        throw new IllegalArgumentException("Too many wildcards (max 31): " + wildcardIndex.size());
    // Collections.reverse(wildcardIndex);
    List<String> output = new ArrayList<>(1 << wildcardIndex.size());
    NEXT: for (;;) {
        output.add(new String(chars));
        for (int i : wildcardIndex) {
            if (chars[i] == '0') {
                chars[i] = '1';
                continue NEXT;
            }
            chars[i] = '0';
        }
        break;
    }
    return output;
}

Тест 1

List<String> output = addCombinations("0?1?");
System.out.println(output);

[0010, 0110, 0011, 0111]

Тест 2

System.out.println(addCombinations("???"));

[000, 100, 010, 110, 001, 101, 011, 111]

Тест 3 (с reverse() вызовом без комментариев)

System.out.println(addCombinations("???"));

[000, 001, 010, 011, 100, 101, 110, 111]