String Comparison

June 21, 2019

We assume the strings are well-formed, with no backspaces that back up the string past its beginning. First we clean the strings to remove all backspace characters and the characters they render invisible:

(define (clean str)
(let loop ((xs (string->list str)) (zs (list)))
(cond ((null? xs) (list->string (reverse zs)))
((char=? (car xs) #\#) (loop (cdr xs) (cdr zs)))
(else (loop (cdr xs) (cons (car xs) zs))))))

Then we compare the cleaned strings:

(define (comp s1 s2) (string=? (clean s1) (clean s2)))

Here’s an example:

> (clean "abcx#de")
"abcde"
> (comp "abcx#de" "abcde")
#t

My first attempt to write this function failed. I kept the strings as strings, used indexes to point to the characters in the strings, and compared the strings at the same time I was backspacing through the removed characters. It was a mess. Separating clean from comp makes the task simpler and the code easier to read.

You can run the program at https://ideone.com/ip8mAg.

Pages: 1 2

8 Responses to “String Comparison”

1. Globules said

import Data.List (foldl')
import Data.Sequence (Seq, (|>))
import qualified Data.Sequence as S
import Text.Printf (IsChar, printf)

-- Apply any backspace elements to the list.
apply :: (a -> Bool) -> [a] -> Seq a
apply isBs = foldl' step S.empty
where step xs x | isBs x    = S.deleteAt (S.length xs - 1) xs
| otherwise = xs |> x

-- True if and only if the two lists are equal after having applied any
-- backspace elements.
eq :: Eq a => (a -> Bool) -> [a] -> [a] -> Bool
eq isBs xs ys = apply isBs xs == apply isBs ys

test :: (Eq a, IsChar a) => (a -> Bool) -> [a] -> [a] -> IO ()
test isBs xs ys = printf "%s == %s?  %s\n" xs ys \$ show (eq isBs xs ys)

main :: IO ()
main = do
test (=='#') "abcx#de" "abcde"
test (=='#') "#abc##" "1#234###a"
test (/='a') "ab" "aa"

\$ ./backspace
abcx#de == abcde?  True
#abc## == 1#234###a?  True
ab == aa?  False

2. Chiklet said

#https://programmingpraxis.com/2019/06/21/string-comparison/

def clean(word):
for i in word:
if i == ‘#’:
if word.index(i) == 0:
word = word[1:]
else:
word = word[0:word.index(i)-1] + word[word.index(i)+1:]
return word

def hashCompare(word1,word2):
word2 = clean(word2)
word1 = clean(word1)
if word1 == word2:
return True
else:
return False

print(str(hashCompare("abcde","abcx#de"))) #true
print(str(hashCompare("#abc##","1#234###a"))) #true
print(str(hashCompare("ab","aa"))) #false

3. Paul said

In Python.

from itertools import zip_longest

def revgen(txt):
"""yields chars in reversed order
"""
deletions = 0
for t in reversed(txt):
if t == "#":
deletions += 1
elif deletions:
deletions -= 1
else:
yield t

def comp(txt1, txt2):
return all(a == b for a, b in zip_longest(revgen(txt1), revgen(txt2), fillvalue=object))

print(comp("ProgrammingPraxis is boring######awesome", "ProgrammingPraxis is awesome"))
# -> True

4. Bill Wood said

In Rust

// CleanIter traverses the string from right to left, removing deleted chars
struct CleanIter<'a> {
it: std::iter::Rev<std::str::Chars<'a>>,
}
impl<'a> Iterator for CleanIter<'a> {
type Item = char;

fn next(&mut self) -> Option<Self::Item> {
let mut n = 0;
while let Some(c) = self.it.next() {
match c {
'#' => n += 1,
_ => {
if n == 0 {
return Some(c);
}
n -= 1;
}
}
}
None
}
}
impl<'a> CleanIter<'a> {
fn new(s: &'a str) -> Self {
CleanIter { it: s.chars().rev() }
}
fn eq(s0: &'a str, s1: &'a str) -> bool {
Self::new(s0).eq(Self::new(s1))
}
}

fn main() {
assert!(CleanIter::eq("abcx#de", "abcx#de"));
assert!(CleanIter::eq("abcx#de", "abcde"));
assert!(CleanIter::eq("#abc##", "1#234###a"));
assert!(CleanIter::eq("12#abc##", "12234###ax###a"));
assert!(!CleanIter::eq("ab", "aa"));
}

5. Bill Wood said

Rust V2

// CleanIter traverses the string from right to left, removing deleted chars
struct CleanIter<'a> {
it: std::iter::Rev<std::str::Chars<'a>>,
}
impl<'a> Iterator for CleanIter<'a> {
type Item = char;

fn next(&mut self) -> Option<Self::Item> {
let mut n = 0;
while let Some(c) = self.it.next() {
match c {
'#' => n += 1,
_ if n == 0 => return Some(c),
_ => n -= 1,
}
}
None
}
}
impl<'a> CleanIter<'a> {
fn new(s: &'a str) -> Self {
CleanIter { it: s.chars().rev() }
}
fn eq(s0: &'a str, s1: &'a str) -> bool {
Self::new(s0).eq(Self::new(s1))
}
}

fn main() {
assert!(CleanIter::eq("abcx#de", "abcx#de"));
assert!(CleanIter::eq("abcx#de", "abcde"));
assert!(CleanIter::eq("#abc##", "1#234###a"));
assert!(CleanIter::eq("12#abc##", "12234###ax###a"));
assert!(!CleanIter::eq("ab", "aa"));
}

6. Daniel said

Here’s a solution in C.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(char* s1, char* s2) {
while (s1 == '#') ++s1;
while (s2 == '#') ++s2;
int i1 = strlen(s1);
int i2 = strlen(s2);
while (1) {
int b1 = 0;
int b2 = 0;
while (i1 >= 0 && s1[i1] == '#') {
++b1;
--i1;
}
while (i2 >= 0 && s2[i2] == '#') {
++b2;
--i2;
}
i1 -= b1;
i2 -= b2;
if (i1 < 0 || i2 < 0) break;
if (s1[i1] != s2[i2]) return 0;
--i1;
--i2;
}
return i1 < 0 && i2 < 0;
}

int main(int argc, char* argv[]) {
if (argc != 3) return EXIT_FAILURE;
printf("%d\n", compare(argv, argv));
return EXIT_SUCCESS;
}

Example Usage:

\$ ./a.out "abcx#de" "abcde"
1

7. Daniel said

Here’s another solution in C.

This approach modifies the strings in-place, then compares.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void delete(char* s) {
int i = 0;
int j = 0;
while (s[j]) {
if (s[j] == '#') {
--i;
if (i < 0) i = 0;
++j;
} else {
s[i] = s[j];
++i;
++j;
}
}
s[i] = '\0';
}

int compare(char* s1, char* s2) {
delete(s1);
delete(s2);
return (strcmp(s1, s2) == 0);
}

int main(int argc, char* argv[]) {
if (argc != 3) return EXIT_FAILURE;
printf("%d\n", compare(argv, argv));
return EXIT_SUCCESS;
}

Example Usage:

\$ ./a.out "abcx#de" "abcde"
1