regex - 两个字符串之间的精确匹配 - 线性编辑距离？

Question

这就是问题所在，给定一个包含以下字符的字符串：a-z、.、*，以及另一个包含来自 的字符的字符串a-z。where*可以删除它之前的字符，否则 * 被跳过并且.可以匹配任何单个字符。问题是第一个字符串是否可以匹配第二个字符串。

注意：这是我发现的问题的陈述，但在这种情况下，字符*执行的功能与?正则表达式中的相同。

例子：

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;

我已经使用稍微修改的编辑距离解决了这个问题，我只知道 2D 动态编程方法。我想知道这个问题是否存在线性解决方案，也许没有 dp 方法可以解决？

Answer 1

感谢@RealzSlaw 的建议。我的问题是寻找一个线性解决方案，这似乎是不可能的，仅仅因为这种情况（现在使用正则表达式语法）：

isMatch("a?a?b?b?b?a?a?b?a?","abbab")

据我所知，它询问是否abbab是 和 的子序列，aabbbaaba这是一个 NP-hard，所以线性解决方案似乎是不可行的。