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.


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

  • 4
    \$\begingroup\$ Welcome to Code Golf! This looks like a reasonably well-specified challenge, but please note we strongly recommend posting your challenges in the Sandbox before putting them on the main site. This question is currently lacking an objective scoring criterion, such as code-golf, and it needs a specification of what regex syntax needs to be supported. \$\endgroup\$
    – pxeger
    Aug 5, 2021 at 8:58
  • 3
    \$\begingroup\$ What regex syntax should be supported? \$\endgroup\$
    – tsh
    Aug 5, 2021 at 9:00
  • 3
    \$\begingroup\$ I edited my question to solve the critical points. \$\endgroup\$
    – user106435
    Aug 5, 2021 at 10:15
  • 2
    \$\begingroup\$ Are there viable approaches for golfing this other than generating all strings of progressively greater Levenshtein distance until you find one matching the regex? \$\endgroup\$
    – xnor
    Aug 5, 2021 at 20:58
  • 2
    \$\begingroup\$ I think the alphabet from which the strings are generated should probably be smaller: many of the chars from Latin-1 have a meaning in regex and would pose some escaping problems while taking the inputs.. not even talking about the non-printable ones.. \$\endgroup\$
    – Kaddath
    Aug 6, 2021 at 9:11

2 Answers 2


PHP, 114 bytes


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"

Crystal, 129 bytes

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

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.