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?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
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.

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

Your Answer

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

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