For regex fans, with explicit caching (memoize)

#!/usr/bin/perl -l

# http://perlmonks.org/?node_id=1197896

use strict;
use warnings;
use List::Util 'min';

my %cache;

sub editDistance
  {
  local $_ = shift;
  $cache{$_} //=
    /(.+)(\0.*)\1$/ ? editDistance("$`$2") :
    /(.)(\0.*)(.)$/ ?
      1 + min map editDistance($_), "$`$2$3", "$`$1$2", "$`$2" :
    length($_) - 1;
  }

my $str1 ="Sundayyyy";
my $str2 = "Saturday";

print editDistance("$str1\0$str2");
[download]