# One-off string detection

Problem spec from CareerCup.

Given two strings, return boolean True/False if they are only one edit apart. Edit can be insert/delete/update of only one character in the string. Eg.

• True

xyz,xz
xyz,xyk
xy,xyz

• False

xyz,xyz
xyz,xzy
x,xyz

module Strings.OneLetter where

import qualified Data.Text as T

oneLetter :: T.Text -> T.Text -> Bool
oneLetter s1 s2
| s1 == s2 = False
| max_l > (min_l + 1) = False
| max_l == min_l = diff_size == 1
| otherwise = diff_size == 0
where
length_s1 = T.length s1
length_s2 = T.length s2
max_l = max length_s1 length_s2
min_l = min length_s1 length_s2
diff_size = length \$ filter (\(a,b) -> a /= b) zipped
zipped = T.zip s1 s2


So, I used Text instead of String, hoping I could take advantage of fusion. I have the following questions and my initial attempt to answer them.

### What is the time complexity of oneLetter?

$0(m+n)$, where $m$ is the length of s1 and $n$ is the length of s2

### what is the space complexity of oneLetter?

I'm thinking due to laziness it's $O(1)$, only two Chars are in memory at any one time, or two Ints. But I'm hazy on why. If this is wrong, please articulate why. If I'm right, and my reasoning is wrong or incomplete, please say why.

### What if I changed from Text to String?

I don't think the time complexity changes, but how does this change the space complexity?

• Your code will return False for "abcdef" "acdef", although both strings only differ by a single deleted character. – Zeta Mar 22 '17 at 20:59
• The space complexity is O(n) in the worst case because texts that differ only in the last letter are forced by the first guard. oneLetter (x:xs) (y:ys) | x == y = oneLetter xs ys; oneLetter x y = x == drop 1 y || drop 1 x == drop 1 y || drop 1 x == y has correct semantics, but still linear space complexity because the disjuncts are evaluated one after the other. Look at the foldl package for constant space. – Gurkenglas Mar 23 '17 at 4:09
• What you're looking for is the "Levenshtein-Distance". Your function then becomes a predicate over an int coming from a function computing the "general problem"... – Vogel612 Mar 23 '17 at 9:33
• @Vogel612 writing an algorithm for the Levenshtein distance is a little bit too much. With the requirements here it's possible to solve the problem in $\mathcal O (1)$ additional space and $\mathcal O(n)$ time. But it's not our job to fix the algorithm. – Zeta Mar 23 '17 at 15:17