World's most popular travel blog for travel bloggers.

[Solved]: exact matching between two strings - linear edit distance?

, , No Comments
Problem Detail: 

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?

Asked By : Kevin Bello

Answered By : Hendrik Jan

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/16260

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback