String Comparison
June 21, 2019
A string is a sequence of characters, perhaps including a backspace character that renders both itself and the previous character as if they were not part of the string. For instance, if we make the backspace character visible using the # symbol, the two strings abcx#de and abcde are identical. Multiple successive backspaces remove multiple successive characters.
Your task is to write a program that compares two strings that may contain backspaces and reports if they are equal. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
A Haskell version.
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"https://pastebin.com/31W4AtR2
#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
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")) # -> TrueIn 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")); }Playground link: https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=d73ac79321dbff905a6105f6ead4754d
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")); }Playground: https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=14beb8ac709eff1e1dfce4b8ca521486
Here’s a solution in C.
#include <stdio.h> #include <stdlib.h> #include <string.h> int compare(char* s1, char* s2) { while (s1[0] == '#') ++s1; while (s2[0] == '#') ++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[1], argv[2])); return EXIT_SUCCESS; }Example Usage:
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[1], argv[2])); return EXIT_SUCCESS; }Example Usage: