给出与正则表达式匹配的字符串的最小Levenshtein距离

Question

在您选择接受它的时候，您的任务是编写一个程序，当给定一个字符串和一个PCRE-regex时，它计算出与正则表达式匹配的另一个字符串的最小Levenshtein距离(完全)。所有字符串，以及正则表达式，都应该在拉丁文-1字符集中。

这是code-golf，所以最短的程序获胜。

两个字符串之间的Levenshtein距离(或编辑距离)是两个字符串的紧密程度，以从一个字符串到另一个字符串所需的操作来度量。一个操作是一个插入、一个删除或一个替换。

示例

a, ab+ -> 1，因为ab与ab+和levenshtein(a, ab) = 1匹配

aaa, .* -> 0，因为aaa匹配

aaaa, ab+a -> 2，因为aba匹配和levenshtein(aaaa, aba) = 2

abcde, a.?b?.?a -> 2，因为abca匹配和levenshtein(abcde, abca) = 2

Answer 1

水晶，129个字节

require"levenshtein"
def f(s,r,d=1/0,a="`")while(a=a.succ).size-s.size<d
d=[d,Levenshtein.distance s,a].min if a[r]?==a
end
d
end

在网上试试！

如果对小写字母的支持就足够了，这就完成了任务。从理论上讲，这不应该有长度的上限--当当前测试字符串a变得如此长时，强制执行循环就会停止，以至于它与输入s之间的Levenshtein距离永远不会小于当前找到的最小距离d。然而，在实践中，即使是最后的测试用例对于TIO来说也太大了。