Give the minimum Levenshtein distance to a string that matches the regex

Question

Your task, at the moment that you choose to accept it, is to write a program that, when given a string and a PCRE-regex, calculates the minimum Levenshtein distance to another string that matches the regex (fully). All strings, as well as the regexes, should be in the Latin-1 character set.

This is code-golf, so the shortest program wins.

The Levenshtein distance (or edit distance) between two strings is the closeness of two strings, measured in operations needed to go from one string to another. One operation is one insertion, one deletion, or one substitution.

Examples

a, ab+ -> 1 because ab matches ab+ and levenshtein(a, ab) = 1

aaa, .* -> 0 because aaa matches

aaaa, ab+a -> 2 because aba matches and levenshtein(aaaa, aba) = 2

abcde, a.?b?.?a -> 2 because abca matches and levenshtein(abcde, abca) = 2

Answer 1

PHP, 114 bytes

for($t=a,$r=INF;$c++<1e8;$t++)preg_match("/^$argv[2]$/",$t)&&($r>$l=levenshtein($argv[1],$t))?$r=$l+$c=0:0;echo$r;

Try it online!

This works with a smaller alphabet and some caveats, but passes the test cases:

• current version only works with lowercase letters (will try to improve this point)
• works by bruteforcing all strings using php strings increment
• uses a counter: the result is output if no smaller levenshtein value is found for a matching string after 100000000 (1e8) string increments (this limit was arbitrarily set to have a result in TIO, as 1e9 times out - can be set up to 9e9 with same byte count)
• following these points, current version will not be able to work if the input string is more than 100000000 (or up to 9e9) string increments from "a"

Answer 2

Crystal, 129 bytes

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

Try it online!

This fulfills the task if support for lowercase alphabet is enough. Theoretically, this shouldn't have an upper limit on length - the bruteforcing loop stops when the current test string a becomes so long that its Levenshtein distance from input s can never be smaller than the currently found minimal distance d. However, in practice, even the last test case is too big for TIO.