The challenge

The method below is the most simple string search algorithm. It will find the first occurrence of a word in a text string.

haystack = the whole text

needle = searchword

wildcard = _

1

find("strike", "i will strike down upon thee"); // return 7

The find method is already made.

The problem is to implement wildcard(s) in the needle. If you have a _ in the needle it will match any character in the haystack.

A normal string search algorithm will find the first occurrence of a word(needle) in a text(haystack), starting on index 0. Like this:

1

find("strike", "I will strike down upon thee"); //return 7

A wildcard in the needle will match any character in the haystack. The method should work on any type of needle, and haystacks. You can assume the needle is shorter than(or equal to) the haystack.

1

find("g__d", "That's the good thing about being president"); // return 11

If no match the method should return -1

The solution in Java code

Option 1:

1
2
3
4
5
6
7
8
9

import java.util.regex.*;
public class SearchEngine {
  static int find(String needle, String haystack){
    String regNeedle = "\\Q" + needle.replaceAll("_", "\\\\E.\\\\Q") + "\\E";
    Matcher m = Pattern.compile(regNeedle).matcher(haystack);
    if(m.find()) return m.start();
    else return -1;
  }
}

Option 2:

1
2
3
4
5
6
7
8
9

import java.util.regex.*;
public class SearchEngine {
  static int find(String needle, String haystack){
    Matcher m = Pattern.compile(
        Pattern.quote(needle).replace("_", "\\E.\\Q")
      ).matcher(haystack);
    return m.find() ? m.start() : -1;
  }
}

Option 3:

1
2
3
4
5
6
7

import static java.util.regex.Pattern.compile;
class SearchEngine {
  static int find(String needle, String haystack) {
    var m = compile("\\Q" + needle.replace("_", "\\E.\\Q") + "\\E").matcher(haystack);
    return m.find() ? m.start() : -1;
  }
}

Test cases to validate our solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

import org.junit.Test;
import static org.junit.Assert.assertEquals;
public class WildsTest {
    String haystack = "Once upon a midnight dreary, while I pondered, weak and weary";    
    @Test
    public void normalSearchTest(){
        assertEquals(0,SearchEngine.find("Once", haystack));
        assertEquals(12, SearchEngine.find("midnight", haystack));
        assertEquals(-1, SearchEngine.find("codewars", haystack));
    }
    @Test
    public void wildSearchTest(){
        assertEquals(5, SearchEngine.find("_po_", haystack));
        assertEquals(12, SearchEngine.find("___night", haystack));
    }
 }