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

[David Turner]

I also think it can be done in one sweep, but I think this code is
O(max(m,n)-min(m,n)): s1' and s2' each appear twice so will be shared.

On 23 March 2017 at 08:52, Andrew Butterfield <
Andrew.Butterfield at scss.tcd.ie> wrote:

> It can be done in one sweep down both strings together - look for the
> first difference,
> and then test hypotheses regarding the 5 possible edits
>
> oneOff :: String -> String -> Bool
>
> oneOff [] [] = False
> oneOff [] (_:rest) = null rest
> oneOff (_:rest) [] = null rest
> oneOff s1@(c1:s1') s2@(c2:s2')
>  | c1 == c2  =  oneOff s1' s2'  -- keep looking
>  | otherwise
>      =    s1' == s2   -- s2 is s1 with c1 deleted or s1 is s2 with c1
> inserted
>        || s2' == s1   -- s1 is s2 with c2 deleted or s2 is s1 with c2
> inserted
>        || s1' == s2'  -- c1 is s1 was replaced by c2 in s2, or v.v.
>
> I guess the above should be O(1) in space - it's just a list crawl with
> tests
> O(n) in the length of the shortest String
>
>
> Cheers,
>   Andrew
>
> On 22 Mar 2017, at 18:48, David Turner <dct25-561bs at mythic-beasts.com>
> wrote:
>
> 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
>>
> _______________________________________________
> 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.
>
>
> Andrew Butterfield
> School of Computer Science & Statistics
> Trinity College
> Dublin 2, Ireland
>
>
> _______________________________________________
> 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/20170323/f86bfc26/attachment.html>