Finding a word within a pre-defined set using a search string with wildcards

The other day I was intrigued by this question (originally from here):


Write a program that answers YES/NO search queries containing * placeholders. Example: if the data you have is (hazem, ahmed,
moustafa, fizo), then you should answer as follows for:

ahmed: YES 
m**stafa: YES 
fizoo: NO
fizd: NO
*****: YES
**: NO

Your program should be able to answer each search query in \$O(1)\$.

I came up with this implementation:

```
class MatcherWithPlaceholders {

protected final Set index = new HashSet<>();

public MatcherWithPlaceholders(List words) {
words.forEach(this::addPermutations);
}

private final void addPermutations(String word) {
char[] letters = word.toCharArray();
for (List starPositions : enumerateStarPositions(word.length())) {
String wordWithStars = getWordWithStars(letters, starPositions);
index.add(wordWithStars);
}
}

private static class ListWithIndex {
final List list;
final int index;

private ListWithIndex(List list, int index) {
this.list = list;
this.index = index;
}
}

protected List> enumerateStarPositions(int length) {
List> results = new LinkedList<>();
results.add(Arrays.asList());

Queue canGrow = new LinkedList<>();
canGrow.add(new ListWithIndex(new LinkedList<>(), 0));

while (!canGrow.isEmpty()) {
ListWithIndex listWithIndex = canGrow.poll();
for (int i = listWithIndex.index; i copy = new LinkedList<>(listWithIndex.list);
copy.add(i);
results.add(copy);
canGrow.add(new ListWithIndex(copy, i + 1));
}
List copy = new LinkedList<>(listWithIndex.list);
copy.add(length - 1);
results.add(copy);
}
return results;
}

private String getWordWithStars(char[] letters, List starPositions) {
char[

I like the solution you use by filling a set with all possible matches. This does indeed make the lookup a \$O(1)\$ operation. The naming, style, and presentation is all fine.

I have a suggestion about the algorithm for computing the permutations of the starred words. When dealing with problems like this it is often most convenient to use bitwise manipulations.This will eliminate the cumbersome storage of the List>. To explain it better, consider the word fizo. This has 4 letters:

fizo
0000  ****
0001  ***o
0010  **z*
0011  **zo
0100  *i**
....
1111  fizo

We can count from 0 to 15 and use the bits in each value to mask out the letters and replace them with the asterisks.

In code, this would look like:

private final void addPermutations(String word) {
    int permutations = 1  index.add(maskChars(mask, word)));
}

private final String maskChars(int mask, String word) {
    char[] clone = word.toCharArray();
    for (int i = 0; i < clone.length; i++) {
        if ((mask & (1 << i)) == 0) {
            clone[i] = '*';
        }
    }
    return new String(clone);
}

In the event that you have word of more than 31 characters, you can swap to using long values. In the event that longs are not enough, use a bitset.... but you probably wold not have enough memory for that anyway ;-)

StackExchange Code Review Q#83031, answer score: 8