World's most popular travel blog for travel bloggers.

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

, ,
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?

#### 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`.