This is the problem, given a string with characters from: a-z, ., *, and another

Question

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?

Explanation / Answer

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.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.