kris1511:

The main reason you're getting the wrong answer is that you're not consistently handling the strings and lengths. Specifically: you're trying to pass the string lengths with the strings so you don't have to modify them, but when you're comparing the specific string endings, you're not taking the string lengths into account. It's probably simpler to just go ahead and modify the strings and pass them around:

use strict;
use warnings;

sub shorten {
    my $tmp = shift;
    return substr($tmp,0,length($tmp)-1);
}

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

sub editDistance {
    my ($l, $lenL, $r, $lenR) = map { $_, length($_) } @_;

    return $lenR unless $lenL;
    return $lenL unless $lenR;

    if (substr($l,-1) eq substr($r,-1)) {
        return editDistance(shorten($l), shorten($r));
    }

    return 1 + min(
        editDistance($l,          shorten($r)), #insert
        editDistance(shorten($l), $r),          #remove
        editDistance(shorten($l), shorten($r))  #replace
    );
}

my @pairs = (
    [ "Sundayyy", "Saturday" ],
    [ "sunday", "saturday" ],
);
for my $ar (@pairs) {
    my ($str1, $str2) = @$ar;
    print editDistance($str1,$str2), " <$str1:$str2>\n";
}

[download]

Update: I just noticed in the docs that substr can take a negative length to remove characters from the end. So if you use substr($x,0,-1) everywhere I used shorten you can drop the shorten function altogether, making the solution a little nicer.

Update 2: Fixed the min routine, as Laurent R observes that my original version would fail miserably if there is a 0 in the list (causing it to terminate prematurely). The example below (with the old min) prints 5. Urk!

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

print "Min test: ", min(5,0,-10), "\n";

[download]

...roboticus

When your only tool is a hammer, all problems look like your thumb.

In reply to Re: Edit Distance Implementation in Perl by roboticus
in thread Edit Distance Implementation in Perl by kris1511

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.