3
$\begingroup$

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.

Example:

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\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$ – Kevin Bello Oct 21 '13 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$ – Hendrik Jan Oct 21 '13 at 22:57
  • $\begingroup$ Now is clear, and yes that particular case would be NP-hard. Thanks! $\endgroup$ – Kevin Bello Oct 22 '13 at 16:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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