## Find The Difference

### January 15, 2019

We consider first a solution that sorts both strings then indexes through them until it finds a difference:

(define (diff1 xstr ystr) (let loop ((xs (sort char<? (string->list xstr))) (ys (sort char<? (string->list ystr)))) (cond ((null? xs) (car ys)) ((char=? (car xs) (car ys)) (loop (cdr xs) (cdr ys))) (else (car ys)))))

> (diff1 "abcdef" "bfxdeac") #\x

That takes time O(*n* log *n*), where *n* is the length of the strings. A better solution operates in time O(*n*):

(define (diff2 xstr ystr) (let ((x (sum (map char->integer (string->list xstr)))) (y (sum (map char->integer (string->list ystr))))) (integer->char (- y x))))

> (diff2 "abcdef" "bfxdeac") #\x

That indexes through the two strings, without sorting, summing the ascii values of the characters in the strings and reporting the difference at the end. You could use XOR instead of addition if you prefer.

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

Scala: (t.toSet–(s.toSet)).iterator.next //> res0: Char = x

Nice one for perl… in the case we are only looking for one known difference it is just finding the letter in the two strings which appears an odd number of times….

If you were looking for all added/removed letters you could change this to:

The %f contains +ve values for letters in $x but not $y and then -ve values for letters in $y but not in $x if that makes sense (and the absolute value is the count of each).

Cool one for basic text processing. Here is my take with Julia 1.0.2:

function StringDifference(s::AbstractString, t::AbstractString)

S = sort(split(s, “”))

T = sort(split(t, “”))

end

#include

#include

#include

using namespace std;

int main()

{

string s1;

string s2;

string s3;

}

Fun exercise! I wouldn’t have thought of the xor on my own.

I also didn’t trust myself to always put the shorter string first, so my solutions allow for supplying the strings in either order.

module Main where

import Data.Bits (xor)

import Data.Char (chr, ord)

import Data.Foldable (foldl')

import qualified Data.Set as S

data Solution a b = S { _in :: String -> a

, _compute :: a -> a -> b

, _out :: b -> Char

}

run :: Solution a b -> String -> String -> Char

run (S i c o) x y = o $ c (i x) (i y)

`s1 :: Solution (S.Set Char) (S.Set Char)`

s1 =

S S.fromList (\x y -> (x

`S.union`

y) S.\\ (x`S.intersection`

y)) S.findMins2 :: Solution Int Int

s2 = S (sum . fmap ord) (-) (chr . abs)

s3 :: Solution Int Int

s3 = S (foldl' xor 0 . fmap ord) xor chr

main :: IO ()

main = do

let x = "abcdef"

y = "bfxdeac"

print $ all (== 'x') [run s1 x y, run s2 x y, run s3 x y]

Sorry, I tried to HTML-escape & post in code tags, but that didn’t work right. Retrying with the WordPress sourcecode attribute:

Clearly, it’s been too long since I visited!

More syntax woes, apologies.

My answer in Python

s = ‘abcdef’

t = ‘cbdefxa’

for c in t:

if c not in s:

print(c)

My C++ is in danger of getting rusty, so let’s use it for a solution. See https://godbolt.org/z/qgGfAe for how the main function compiles.

That needs C++14 features, so build with eg:

Python solution using sets (similar to Haskell s1 solution above).

Three Python solutions.

Python solution.

Works when s or t have duplicate letters (set solutions don’t).

Stops when the new letter is found, so it may not process the entire string.

@Mike: doesn’t that assume that the characters haven’t been shuffled? Good point on use of sets though.

Here’s a more streamlined version of my C++ solution:

Another Haskell version.

@Graham, I use the following shell script to create comments here.

EOF

test -z "$cmd" || {

echo "

"

}

[/code]

I run it like

then just paste the output in the comment widget.

LOL! I feel your pain. :-)

Here are a few approaches in C. The table-driven approach was my initial implementation. It counts each letter and then compares the counts. The other approaches were inspired by the solution: an XOR approach, a sum approach, and a sorting approach.

Example:

I forgot to free my memory allocations :-(.

Here’s an update.

The fastest solution I could find in Python.

Prolog solution here (not optimized):

Then just