This is the problem, given a string with characters from: a-z, ., *, and another string with characters from a-z. where * 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?


1 Answer 1


As far as I understand you cannot solve the problem in linear time. If in the first string every character a-z is followed by *, the problem coincides with substring matching. So, isMatch("a?a?b?b?b?a?b?a?b?a?","abba") asks whether abba is a subsequence of aabbbababa.

  • $\begingroup$ Thanks for responding.That particular case could be solved by a linear algorithm like KMP. I'm pretty sure you know that, for that reason it's not clear to me. $\endgroup$ Oct 21, 2013 at 14:17
  • $\begingroup$ @KevinBelloMedina My mistake. I said "substring" but a better name would be "subsequence" (which is not KMP, and seems to need quadratic dynamic programming). $\endgroup$ Oct 21, 2013 at 22:57
  • $\begingroup$ Now is clear, and yes that particular case would be NP-hard. Thanks! $\endgroup$ Oct 22, 2013 at 16:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.