• 1

• 113k
• 15
• 154
• 396

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<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 tests

public 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.