In search of elegant code - do two strings differ by one character?

Discussion in 'Perl Misc' started by usenet@DavidFilmer.com, Aug 1, 2005.

  1. Guest

    I wish to construct a subroutine which will accept two strings and
    return True if they differ by ONLY one "extra" character
    (case-sensitive). For example, it would return true if passed qw/Perl
    Pearl/, but false for qw/Perl Preal/. It would be nice if it could also
    identify single-character variances (without an additional character,
    ie, qw/Perl Pell/ or qw/Perl perl/)

    I suspect there's a module that will save me the bother of writing an
    ugly, brute-force, one-character-at-a-time parser/comparitor. I had a
    look at Text::Diff but it doesn't seem to fill this particular need
    (and, of course, it's not designed to). And I looked at a few others as
    well, but no luck (I couldn't even figure out what Text::Compare is
    supposed to do!).

    I can write the ugly code (I'm pretty good at that!), but I'd
    appreciate anyone who can refer me to something better.
     
    , Aug 1, 2005
    #1
    1. Advertising

  2. wrote:
    > I wish to construct a subroutine which will accept two strings and
    > return True if they differ by ONLY one "extra" character
    > (case-sensitive). For example, it would return true if passed qw/Perl
    > Pearl/, but false for qw/Perl Preal/. It would be nice if it could also
    > identify single-character variances (without an additional character,
    > ie, qw/Perl Pell/ or qw/Perl perl/)
    >
    > I suspect there's a module that will save me the bother of writing an
    > ugly, brute-force, one-character-at-a-time parser/comparitor. I had a
    > look at Text::Diff but it doesn't seem to fill this particular need
    > (and, of course, it's not designed to). And I looked at a few others as
    > well, but no luck (I couldn't even figure out what Text::Compare is
    > supposed to do!).
    >
    > I can write the ugly code (I'm pretty good at that!), but I'd
    > appreciate anyone who can refer me to something better.


    It looks like you might need a Levenshtein Distance algorithm or
    something similar.

    Here is a Perl version of one:

    sub levenshtein {
    my ( $A, $B ) = @_;
    my ( $len_A, $len_B ) = ( length $A, length $B );
    return $len_B unless $len_A;
    return $len_A unless $len_B;

    my @W = 0 .. $len_B;
    my $next;
    for my $i ( 0 .. $len_A - 1 ) {
    my $cur = $i + 1;
    for my $j ( 0 .. $len_B - 1 ) {
    my ( $x, $y, $z ) =
    ( $W[ $j + 1 ] + 1,
    $cur + 1,
    $W[ $j ] + ( substr($A,$i,1) ne substr($B,$j,1) )
    );
    $W[ $j ] = $cur;
    $cur = $next = $x < $y && $x < $z ? $x : $y < $z ? $y : $z;
    }
    $W[ $len_B ] = $next;
    }
    return $next;
    }



    John
    --
    use Perl;
    program
    fulfillment
     
    John W. Krahn, Aug 1, 2005
    #2
    1. Advertising

  3. Anno Siegel Guest

    <> wrote in comp.lang.perl.misc:
    > I wish to construct a subroutine which will accept two strings and
    > return True if they differ by ONLY one "extra" character
    > (case-sensitive). For example, it would return true if passed qw/Perl
    > Pearl/, but false for qw/Perl Preal/. It would be nice if it could also
    > identify single-character variances (without an additional character,
    > ie, qw/Perl Pell/ or qw/Perl perl/)
    >
    > I suspect there's a module that will save me the bother of writing an
    > ugly, brute-force, one-character-at-a-time parser/comparitor. I had a
    > look at Text::Diff but it doesn't seem to fill this particular need
    > (and, of course, it's not designed to). And I looked at a few others as
    > well, but no luck (I couldn't even figure out what Text::Compare is
    > supposed to do!).


    Search CPAN for "approx", it should come up with something.

    > I can write the ugly code (I'm pretty good at that!), but I'd
    > appreciate anyone who can refer me to something better.


    sub one_extra {
    my ( $short, $long) = @_;
    return 0 unless 1 + length $short == length $long;
    grep $_ eq $short, map { substr( my $t = $long, $_, 1, ''); $t}
    0 .. length $short;
    }

    Anno
    --
    If you want to post a followup via groups.google.com, don't use
    the broken "Reply" link at the bottom of the article. Click on
    "show options" at the top of the article, then click on the
    "Reply" at the bottom of the article headers.
     
    Anno Siegel, Aug 1, 2005
    #3
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. yogi_bear_79
    Replies:
    2
    Views:
    250
    yogi_bear_79
    Mar 11, 2008
  2. David Filmer
    Replies:
    9
    Views:
    111
  3. David Filmer

    In search of elegant code: inverting a string

    David Filmer, Oct 29, 2003, in forum: Perl Misc
    Replies:
    9
    Views:
    123
    Russ Jones
    Oct 30, 2003
  4. David Filmer
    Replies:
    11
    Views:
    218
    Brad Baxter
    Dec 5, 2003
  5. David Filmer
    Replies:
    3
    Views:
    158
    Heinrich Mislik
    Sep 22, 2004
Loading...

Share This Page