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: NOfizd: NO*****: YES**: NOYour program should be able to answer each search query in \$O(1)\$.I came up with this implementation:class MatcherWithPlaceholders {    protected final Set<String> index = new HashSet<>();    public MatcherWithPlaceholders(List<String> words) {        words.forEach(this::addPermutations);    }    private final void addPermutations(String word) {        char[] letters = word.toCharArray();        for (List<Integer> starPositions : enumerateStarPositions(word.length())) {            String wordWithStars = getWordWithStars(letters, starPositions);            index.add(wordWithStars);        }    }    private static class ListWithIndex {        final List<Integer> list;        final int index;        private ListWithIndex(List<Integer> list, int index) {            this.list = list;            this.index = index;        }    }    protected List<List<Integer>> enumerateStarPositions(int length) {        List<List<Integer>> results = new LinkedList<>();        results.add(Arrays.asList());        Queue<ListWithIndex> canGrow = new LinkedList<>();        canGrow.add(new ListWithIndex(new LinkedList<>(), 0));        while (!canGrow.isEmpty()) {            ListWithIndex listWithIndex = canGrow.poll();            for (int i = listWithIndex.index; i < length - 1; ++i) {                List<Integer> copy = new LinkedList<>(listWithIndex.list);                copy.add(i);                results.add(copy);                canGrow.add(new ListWithIndex(copy, i + 1));            }            List<Integer> copy = new LinkedList<>(listWithIndex.list);            copy.add(length - 1);            results.add(copy);        }        return results;    }    private String getWordWithStars(char[] letters, List<Integer> starPositions) {        char[] copy = letters.clone();        for (int pos : starPositions) {            copy[pos] = '*';        }        return new String(copy);    }    public boolean hasMatch(String word) {        return index.contains(word);    }}Unit testspublic class MatcherWithPlaceholdersTest {    private MatcherWithPlaceholders matcher =            new MatcherWithPlaceholders(Arrays.asList(hazem, ahmed, moustafa, fizo));    private boolean hasMatch(String query) {        return matcher.hasMatch(query);    }    @Test    public void test_enumerateStarPos_1() {        assertEquals([[], [0]], matcher.enumerateStarPositions(1).toString());    }    @Test    public void test_enumerateStarPos_2() {        assertEquals([[], [0], [1], [0, 1]],                matcher.enumerateStarPositions(2).toString());    }    @Test    public void test_enumerateStarPos_3() {        assertEquals([[], [0], [1], [2], [0, 1], [0, 2], [1, 2], [0, 1, 2]],                matcher.enumerateStarPositions(3).toString());    }    @Test    public void test_ahmed() {        assertTrue(hasMatch(ahmed));    }    @Test    public void test_m00stafa() {        assertTrue(hasMatch(m**stafa));    }    @Test    public void test_00() {        assertFalse(hasMatch(**));    }    @Test    public void test_0000() {        assertTrue(hasMatch(****));    }    @Test    public void test_00000() {        assertTrue(hasMatch(*****));    }    @Test    public void test_000000000000000() {        assertFalse(hasMatch(***************));    }    @Test    public void test_fizoo() {        assertFalse(hasMatch(fizoo));    }    @Test    public void test_fizd() {        assertFalse(hasMatch(fizd));    }}The implementation works fine, unit tests passing,and it's \$O(1)\$ if you don't count the hashing of the input string to perform the lookup.Of course space is sacrificed here for speed.I'm wondering if it's possible to improve the implementation.I find the permutation part a bit awkward,and have the feeling there's a cleaner, more elegant way to do that.I'm also interested in other improvement ideas as well,including the main algorithm / approach.
Finding a word within a pre-defined set using a search string with wildcards
java;programming challenge;search;combinatorics;rags to riches
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<List<Integer>>. To explain it better, consider the word fizo. This has 4 letters:fizo0000  ****0001  ***o0010  **z*0011  **zo0100  *i**....1111  fizoWe 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 << word.length();    IntStream.range(0,permutations).forEach(mask -> 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 ;-)