Check whether a list of list of string fits a regex efficiently I have the following structure for my object:

Word (Object)


Word (String)
List&lt;Symbol&gt;


Symbol (Object)


Symbol (String)
List&lt;SymbolChoice&gt;


SymbolChoice (Object)


Symbol (String)


The background of this is that this is processed OCR output and I want to force a word to match a certain regex. If it cannot find a match, it should return an empty List&lt;SymbolChoice&gt;, otherwise it should return all List&lt;SymbolChoice&gt; that match the specified regex.

Example:


Found word: "1o0"
Symbols: "1", "o" and "0"
Choices of "1": "1"
Choices of "o": "o", "0"
Choices of "0": "0"


When forcing this word to abide regex "\\d{3}", it has to return [["1", "0", "0"]], here I am denoting the SymbolChoice objects as strings.

I have a solution, however it is not fast enough, more details after the method:

public List&lt;List&lt;SymbolChoice&gt;&gt; forceFitRegex(final String regex) {
    Objects.requireNonNull(regex, "regex");

    if (getSymbols().size() &lt;= 1) {
        return new ArrayList&lt;List&lt;SymbolChoice&gt;&gt;();
    }

    int combinations = 1;
    for (Symbol symbol : getSymbols()) {
        combinations *= symbol.getSymbolChoices().size();
    }
    System.out.println("Combinations: " + combinations);

    List&lt;List&lt;SymbolChoice&gt;&gt; listOfSymbolChoices = new ArrayList&lt;List&lt;SymbolChoice&gt;&gt;();
    for (SymbolChoice symbolChoice : getSymbols().get(0).getSymbolChoices()) {
        List&lt;SymbolChoice&gt; symbolChoices = new ArrayList&lt;SymbolChoice&gt;();
        symbolChoices.add(symbolChoice);
        listOfSymbolChoices.add(symbolChoices);
    }

    int i = 1;
    while (i &lt; getSymbols().size()) {
        List&lt;List&lt;SymbolChoice&gt;&gt; listOfSymbolChoicesCopy = new ArrayList&lt;List&lt;SymbolChoice&gt;&gt;(listOfSymbolChoices);
        for (SymbolChoice symbolChoice : getSymbols().get(i).getSymbolChoices()) {
            for (List&lt;SymbolChoice&gt; symbolChoicesCopy : listOfSymbolChoicesCopy) {
                List&lt;SymbolChoice&gt; symbolChoices = new ArrayList&lt;SymbolChoice&gt;(symbolChoicesCopy);
                symbolChoices.add(symbolChoice);
                listOfSymbolChoices.add(symbolChoices);
            }
        }
        i++;
    }

    Pattern pattern = Pattern.compile(regex);
    ListIterator&lt;List&lt;SymbolChoice&gt;&gt; symbolChoicesListIterator = listOfSymbolChoices.listIterator();
    while (symbolChoicesListIterator.hasNext()) {
        List&lt;SymbolChoice&gt; symbolChoices = symbolChoicesListIterator.next();
        StringBuilder stringBuilder = new StringBuilder();
        for (SymbolChoice symbolChoice : symbolChoices) {
            stringBuilder.append(symbolChoice.getSymbol());
        }
        if (!pattern.matcher(stringBuilder.toString()).matches()) {
            symbolChoicesListIterator.remove();
        }
    }
    return listOfSymbolChoices;
}


Let n be the number of combinations possible, calculated as the product of the size of all symbol choices. In my example that would be 1 * 2 * 1 = 2.

For n &lt;= 288 I observe it to run very quick, however with for example n = 5760 it takes a few minutes to process. I also spot here another case of n = 311040 and have a feeling that it will never finish.

What can I do to solve my problem efficiently? I need to stick to Java 6 for Android compatibility.

(Bonus points if someone can calculate the asymptotic time my algorithm takes)
Bonus points if someone can calculate the asymptotic time my algorithm takes.

Too much. It's exponential, as you're generating the whole candidate set. Even the improvement by rolfl doesn't change it.
You could do much better by analyzing the regex. For example &quot;\\d{3}&quot; will never match anything starting with a letter and you could cut off many possibilities. However, doing this in general is pretty complicated.
There's a method which might do this for you: hitEnd. I'm not sure if it does the right thing, but I guess so:

Returns true if the end of input was hit by the search engine in the last match operation performed by this matcher.
When this method returns true, then it is possible that more input would have changed the result of the last search.

So you could test you incomplete candidates against the regex and possibly save yourself the work with expanding them.