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.

Advertisements

Pages: 1 2

8 Responses to “String Comparison”

  1. Globules said

    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"
    
    $ ./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"));
    }
    

    Playground link: https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=d73ac79321dbff905a6105f6ead4754d

  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"));
    }
    

    Playground: https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=14beb8ac709eff1e1dfce4b8ca521486

  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[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:

    $ ./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[1], argv[2]));
      return EXIT_SUCCESS;
    }
    

    Example Usage:

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: