Generating all binary numbers based on the pattern

Question

Given a pattern , we need to generate all possible binary numbers by filling the missing places in the pattern by 0 and 1.

E.g. Pattern = "x1x";
Output =  [010, 110, 011, 111]

I solved it by creating a method calculate.

public static List<String> calculate(String input, int currentIndex) {
    List<String> result = new ArrayList<String>();
    if(currentIndex > input.length()-1) {
        result.add("");
        return result;
    }
    for(String fragment: calculate(input, currentIndex + 1)) {
        if(input.charAt(currentIndex)=='x') {
            result.add('0' + fragment);
            result.add('1' + fragment);
        }
        else {
            result.add(input.charAt(currentIndex) + fragment);
        }
    }
    return result;
}

Is there some way in which we can leverage the given pattern and design a much Faster and/or cleaner solution. I already know that non-recursive solution will be better. Java 8 features are also welcome.

Answer 1

On reflection, using recursion and a call back is much more efficient way of doing this. Note: this creates very few objects (possibly 3 regardless of the number of results).

public static void main(String[] args) {
    printForPattern("x1x", System.out::println);
}

private static void printForPattern(String pattern, Consumer<CharSequence> consumer) {
    printForPattern(pattern, new StringBuilder(), consumer);
}

private static void printForPattern(String pattern, StringBuilder sb, Consumer<CharSequence> consumer) {
    int length = sb.length();
    if (pattern.length() == length) {
        consumer.accept(sb);
        return;
    }
    char ch = pattern.charAt(length);
    if (ch == 'x' || ch == '0') {
        sb.append('0');
        printForPattern(pattern, sb, consumer);
        sb.setLength(length);
    }
    if (ch == 'x' || ch == '1') {
        sb.append('1');
        printForPattern(pattern, sb, consumer);
        sb.setLength(length);
    }
}

To add this to a list you can do

List<String> results = ...
printForPattern("x1x", s -> results.add(x.toString()));

---

You can;

• count the number of wildcards or xs. This is the number of bits you need to iterate over.
• iterate over 2^^{number of x's) and this will give you all possible bits for those x.
• merge these generated x with the provided bit pattern.

share | improve this answer | follow |

查看更多

0人赞 添加讨论(0) 举报