use strict;
use warnings;

sub min {
    my $rv = shift;
    for my $tmp (@_) {
        $rv = $tmp if $tmp < $rv;
    }
    return $rv;
}

sub editDistance {
    my ($left, $lenLeft, $right, $lenRight) = map { $_, length($_) } @_;

    return $lenRight unless $lenLeft;
    return $lenLeft unless $lenRight;
    
    my $shortLeft  = substr $left,  0, -1;
    my $shortRight = substr $right, 0, -1;
    return editDistance ($shortLeft, $shortRight) if substr($left, -1) eq substr($right, -1);

    return 1 + min(
        editDistance($left,       $shortRight), #insert
        editDistance($shortLeft,  $right),      #remove
        editDistance($shortLeft,  $shortRight)  #replace
    );
}

##</code><code>##

$ time perl editDistance.pl
11 <LMIjkHFSAE:dmqkdjfERZG>

real    2m29.329s
user    1m2.578s
sys     1m26.452s

##</code><code>##

$ time perl editDistance.pl
11 <LMIjkHFSAE:dmqkdjfERZG>

real    0m0.075s
user    0m0.015s
sys     0m0.030s

##</code><code>##

use strict;
use warnings;
use Memoize;

sub min {
    my $rv = shift;
    for my $tmp (@_) {
        $rv = $tmp if $tmp < $rv;
    }
    return $rv;
}

sub editDistance {
    my ($left, $lenLeft, $right, $lenRight) = map { $_, length($_) } @_;

    return $lenRight unless $lenLeft;
    return $lenLeft unless $lenRight;
    
    my $shortLeft  = substr $left,  0, -1;
    my $shortRight = substr $right, 0, -1;
    return editDistance ($shortLeft, $shortRight) if substr($left, -1) eq substr($right, -1);

    return 1 + min(
        editDistance($left,       $shortRight), #insert
        editDistance($shortLeft,  $right),      #remove
        editDistance($shortLeft,  $shortRight)  #replace
    );
}

memoize("editDistance");
editDistance(...);