Write a function that performs searching for a string in a piece of text. The string for which to be searched, however, may contain asterisks (*) representing a wildcard for any sequence of characters or none.

The followings are expected outputs:

search(“This is a book”, “book”); // returns true
search(“This is a book”, “books”); // returns false
search(“This is a book”, “t*is a”); // returns true
search(“This is a book”, “is*his*oo”); // returns false
search(“This is a book”, “th*s*ok”); // returns true

Your solution:

I encourage you to get your hands dirty a bit before scrolling down to see my solution. Please do not concern with the performance issue for now.

.
.
.
.

My solution:

When encountering such a kind of problems, people will first think of using loops (particularly nested loops) in their solution. From another point of view, I would like to introduce a solution using functional recursion without using a single loop.

1
2
3
4
5
6
7
8

 bool search(char *text, char *word, bool det = false){
    return *word  == '\0' ? true :
           *text == '\0' ? false :
           det == false || *word == '*' ?
              search(text, word+1, true) ||
              search(text+1, word) :
           *text == *word && search(text+1, word+1, true);
}

Note that this problem indirectly involves non-determinism which may not be solved with ease. Many problem solvers usually end up with complicated solutions and may not work for all test cases.

Any comments are welcome.