This is the problem, given a string with characters from:
*, and another string with characters from
* can delete the character before it, otherwise
* is skipped and
. can match any single character. the question is whether the first string can match the second one.
Note: That is the statement of the problem as I found, but in this case the character
* performs the same function that
? in a regular expression.
isMatch("a*", "") = true; //"a*" could be "a" or an empty string "" isMatch(".", "") = false; isMatch("ab*", "a") = true; isMatch("a.", "ab") = true; isMatch("a", "a") = true;
I've already solved this problem using a slightly modified edit distance, which I only know a 2D dynamic programming approach. I wonder whether exists a linear solution for this problem, maybe it is solvable without a dp approach?