Task — Backspace compare

You are given two strings containing zero or more '#'. Write a script to return true if the two given strings are same by treating # as backspace.

Examples

Example 1
Input: $str1 = 'ab#c'
       $str2 = 'ad#c'
Output: true
For first string,  we remove 'b' as it is followed by '#'.
For second string, we remove 'd' as it is followed by '#'.
In the end both strings became the same.

Example 2
Input: $str1 = 'ab##'
       $str2 = 'a#b#'
Output: true

Example 3
Input: $str1 = 'a#b'
       $str2 = 'c'
Output: false

Analysis

'Backspace' is a word which harks back to the days of typewriters, and the early computer i/o devices based on them. On those devices, 'a#b' (in the terminology of this challenge) would print b on top of a. The ASCII and Unicode character for that backspace is code point 0x8, denoted BS.

Related to that is code point 0x7F DEL, which is interpreted as nothing at all: the character after DEL is to be treated as coming immediately after the one before DEL. In the days of paper tape, an incorrect character could be deleted by punching out all 8 columns, yielding a value of 7F with the parity bit set.

However, neither of these interpretations apply in this challenge: rather, we deduce from the examples that a string of n '#' characters requires us to delete the n letters immediately preceding them. We are not told what to do if there aren't n preceding characters, and I have lazily assumed in that case we do nothing - so 'ab###' resolves to '#', because after deleting 'b#' and 'a#' nothing matches '.#'.

So how do we solve the challenge? The heart of my solution is

$z = 1; $z = ($string =~ s|.#||) while $z;

This works because the s||| operator in scalar context returns the number of substitutions it has made. So the while repeats the substitutions until there are no more .# substrings. Note that we can't use s|.#||g because the s does not backtrack. Given, for example, ab## it will match b# but won't go back and consider a#.

Doing that on both strings and comparing them gives us the desired result.

Try it 

#!/usr/bin/perl

# Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge

use v5.26;    # The Weekly Challenge - 2025-05-12
use utf8;     # Week 321 - task 2 - Backspace compare
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';
use Encode;

backspace_compare('ab#c', 'ad#c');
backspace_compare('ab##', 'a#b#');
backspace_compare('same', 'same');
backspace_compare('#same', '#same');
backspace_compare('a#b', 'c');
backspace_compare('the curfewww## tolls the knelllll### of paaaaa####rting day', 
                  'z#the curfew tollxx##s the knell ofzzz### parting dayw#');

sub backspace_compare {
    
    my ($string1, $string2, $z, $s);
    
    # initialise
    ($string1, $string2) = @_;
    say qq[\nInput:  \$string1 = '$string1',\n        \$string2 = '$string2'];
    
    # repeatedly delete backspace and preceding character
    for $s ($string1, $string2) {
        $z = 1;
        $z = ($s =~ s|.#||) while $z;
    }
    
    # report
    say qq[Output: ] . ($string1 eq $string2 ? qq[true -     '$string1'] : 
        qq[false -    '$string1' vs '$string2']);
}

Output

Input:  $string1 = 'ab#c',
        $string2 = 'ad#c'
Output: true -     'ac'

Input:  $string1 = 'ab##',
        $string2 = 'a#b#'
Output: true -     ''

Input:  $string1 = 'same',
        $string2 = 'same'
Output: true -     'same'

Input:  $string1 = '#same',
        $string2 = '#same'
Output: true -     '#same'

Input:  $string1 = 'a#b',
        $string2 = 'c'
Output: false -    'b' vs 'c'

Input:  $string1 = 'the curfewww## tolls the knelllll### 
   of paaaaa####rting day',
        $string2 = 'z#the curfew tollxx##s the knell 
   ofzzz### parting dayw#'
Output: true -     'the curfew tolls the knell of parting 
   day'