[Haskell-cafe] One-Off detection. Question about Space/Time complexity

[David Turner]

I think the space must be O(m+n) since you are using strict Text values.
But even if you weren't, you're using s1 and s2 in more than one place so
they will be shared, leading to them both being fully in memory at once.

The minimum possible space complexity could well be O(1) if using String or
lazy Text.

The time complexity looks like O(min(m,n)), because that's the cost of
`zip`/`filter`, not counting the cost of loading the two Texts into memory
in the first place (which will be O(m+n)). If you used String, it'd be
O(m+n) since that's the cost of the two calls to `length`. I think the
minimum possible time complexity will be O(min(m,n)), and that could
include the cost of loading the strings too.

On 22 Mar 2017 18:32, "Michael Litchard" <litchard.michael at gmail.com> wrote:

> Problem spec from CareerCup
> <https://careercup.com/question?id=5092486548553728>.
>
> 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 Preludeimport 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.
>
> I don't think I can improve the time complexity. Am I right? Can the space
> complexity be improved?
>
> What if I changed from Text to String? I don't think the time complexity
> changes, but how does this change the space complexity?
>
>
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> To (un)subscribe, modify options or view archives go to:
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
> Only members subscribed via the mailman list are allowed to post
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20170322/8e11b55b/attachment.html>