<html><head><meta http-equiv="Content-Type" content="text/html charset=us-ascii"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class="">Yes - they both might be scanned twice, but O(2n) = O(n) = O(3n), even.<div class=""><br class=""></div><div class="">The scanniing by the three uses of == only walk over *all* of the longer list if its length is at most that of the shorter</div><div class=""><br class=""></div><div class="">Simply put, if s1 is much longer than s2, then those == scans will end when they reach the end of the shorter s2</div><div class=""><br class=""></div><div class="">Or am I missing something?</div><div class=""><br class=""></div><div class=""><div><blockquote type="cite" class=""><div class="">On 23 Mar 2017, at 15:19, David Turner <<a href="mailto:dct25-561bs@mythic-beasts.com" class="">dct25-561bs@mythic-beasts.com</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div dir="ltr" class="">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.</div></div></blockquote><div><br class=""></div>if m == n your timing reduces to O(0) !?<br class=""><blockquote type="cite" class=""><div class=""><div class="gmail_extra"><br class=""><div class="gmail_quote">On 23 March 2017 at 08:52, Andrew Butterfield <span dir="ltr" class=""><<a href="mailto:Andrew.Butterfield@scss.tcd.ie" target="_blank" class="">Andrew.Butterfield@scss.tcd.ie</a>></span> wrote:<br class=""><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word" class="">It can be done in one sweep down both strings together - look for the first difference,<div class="">and then test hypotheses regarding the 5 possible edits</div><div class=""><br class=""></div><div class=""><div class="">oneOff :: String -> String -> Bool</div><div class=""><br class=""></div><div class="">oneOff [] [] = False</div><div class="">oneOff [] (_:rest) = null rest</div><div class="">oneOff (_:rest) [] = null rest</div><div class="">oneOff s1@(c1:s1') s2@(c2:s2')</div><div class=""> | c1 == c2 = oneOff s1' s2' -- keep looking</div><div class=""> | otherwise </div><div class=""> = s1' == s2 -- s2 is s1 with c1 deleted or s1 is s2 with c1 inserted </div><div class=""> || s2' == s1 -- s1 is s2 with c2 deleted or s2 is s1 with c2 inserted</div><div class=""> || s1' == s2' -- c1 is s1 was replaced by c2 in s2, or v.v.</div></div><div class=""><br class=""></div><div class=""><div class="">I guess the above should be O(1) in space - it's just a list crawl with tests</div><div class="">O(n) in the length of the shortest String<br class=""><blockquote type="cite" class=""><div dir="auto" class=""></div></blockquote></div></div><div class=""><br class=""></div><div class="">Cheers,</div><div class=""> Andrew</div><div class=""><br class=""></div><div class=""><div class=""><div class="h5"><div class=""><blockquote type="cite" class=""><div class="">On 22 Mar 2017, at 18:48, David Turner <<a href="mailto:dct25-561bs@mythic-beasts.com" target="_blank" class="">dct25-561bs@mythic-beasts.com</a><wbr class="">> wrote:</div><br class="m_-4550398139290822214Apple-interchange-newline"><div class=""><div dir="auto" class=""><div class="">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.</div><div dir="auto" class=""><br class=""></div><div dir="auto" class="">The minimum possible space complexity could well be O(1) if using String or lazy Text.</div></div></div></blockquote><div class=""><br class=""></div></div></div></div><div class=""><blockquote type="cite" class=""><div class=""><div class=""><div class="h5"><div dir="auto" class=""><div dir="auto" class=""><br class=""></div><div dir="auto" class="">The time complexity looks like <span style="font-family:sans-serif" class="">O(min(m,n)),</span> 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 <span style="font-family:sans-serif" class="">O(min(m,n)), and that could include the cost of loading the strings too.</span></div><div dir="auto" class=""><div class="gmail_extra" dir="auto"><br class=""><div class="gmail_quote">On 22 Mar 2017 18:32, "Michael Litchard" <<a href="mailto:litchard.michael@gmail.com" target="_blank" class="">litchard.michael@gmail.com</a>> wrote:<br type="attribution" class=""><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr" class=""><div class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-post-text"><p class="">Problem spec from <a rel="nofollow noreferrer" href="https://careercup.com/question?id=5092486548553728" target="_blank" class="">CareerCup</a>.</p><p class="">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.</p><p class="">-True</p><p class="">xyz,xz</p><p class="">xyz,xyk</p><p class="">xy,xyz</p><p class="">-False</p><p class="">xyz,xyz</p><p class="">xyz,xzy</p><p class="">x,xyz</p>
<pre class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-lang-hs m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-prettyprinted m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-prettyprint"><code class=""><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-kwd">module</span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-pln"> Strings.OneLetter </span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-kwd">where</span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-pun">`</span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-pln">
</span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-kwd">import</span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-pln"> Prelude
</span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-kwd">import</span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-pln"> qualified Data.Text as T</span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-pun">`</span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-pln">
oneLetter </span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-pun">::</span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-pln"> T.Text </span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-pun">-></span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-pln"> T.Text </span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-pun">-></span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-pln"> Bool
oneLetter s1 s2
</span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-pun">|</span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-pln"> s1 </span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-pun">==</span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-pln"> s2 </span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-pun">=</span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-pln"> False
</span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-pun">|</span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-pln"> max_l </span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-pun">></span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-pln"> </span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-pun">(</span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-pln">min_l </span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-pun">+</span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-pln"> </span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-lit">1</span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-pun">)</span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-pln"> </span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-pun">=</span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-pln"> False
</span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-pun">|</span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-pln"> max_l </span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-pun">==</span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-pln"> min_l </span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-pun">=</span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-pln"> diff_size </span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-pun">==</span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-pln"> </span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-lit">1</span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-pln">
</span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-pun">|</span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-pln"> otherwise </span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-pun">=</span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-pln"> diff_size </span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-pun">==</span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-pln"> </span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-lit">0</span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-pln">
</span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-kwd">where</span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-pln">
length_s1 </span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-pun">=</span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-pln"> T.length s1
length_s2 </span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-pun">=</span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-pln"> T.length s2
max_l </span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-pun">=</span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-pln"> max length_s1 length_s2
min_l </span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-pun">=</span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-pln"> min length_s1 length_s2
diff_size </span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-pun">=</span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-pln"> length </span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-pun">$</span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-pln"> filter </span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-pun">(\(</span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-pln">a</span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-pun">,</span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-pln">b</span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-pun">)</span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-pln"> </span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-pun">-></span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-pln"> a </span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-pun">/=</span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-pln"> b</span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-pun">)</span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-pln"> zipped
zipped </span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-pun">=</span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-pln"> T.zip s1 s2</span><span class="m_-4550398139290822214m_3781259659987824222m_4002822050704418726gmail-pun">`</span></code></pre><p class="">So, I used <code class="">Text</code> instead of <code class="">String</code>, hoping I could take advantage of fusion. I have the following questions and my initial attempt to answer them.</p><p class="">What is the time complexity of <code class="">oneLetter</code>
0(m+n) where m is the length of <code class="">s1</code> and n is the length of <code class="">s2</code></p><p class="">what is the space complexity of <code class="">oneLetter</code>?
I'm thinking due to laziness it's O(1), only two <code class="">Char</code>s are in memory at any one time, or two <code class="">Int</code>s.
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.</p><p class="">I don't think I can improve the time complexity. Am I right? Can the space complexity be improved?<br class=""></p><p class="">What if I changed from <code class="">Text</code> to <code class="">String</code>?
I don't think the time complexity changes, but how does this change the space complexity?</p><p class=""><br class=""></p><p class=""><br class=""></p>
</div></div>
<br class="">______________________________<wbr class="">_________________<br class="">
Haskell-Cafe mailing list<br class="">
To (un)subscribe, modify options or view archives go to:<br class="">
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe" rel="noreferrer" target="_blank" class="">http://mail.haskell.org/cgi-bi<wbr class="">n/mailman/listinfo/haskell-caf<wbr class="">e</a><br class="">
Only members subscribed via the mailman list are allowed to post<br class=""></blockquote></div></div>
</div></div>
______________________________<wbr class="">_________________<br class="">Haskell-Cafe mailing list<br class="">To (un)subscribe, modify options or view archives go to:<br class=""><a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe" target="_blank" class="">http://mail.haskell.org/cgi-<wbr class="">bin/mailman/listinfo/haskell-<wbr class="">cafe</a><br class=""></div></div>Only members subscribed via the mailman list are allowed to post.</div></blockquote></div><span class="HOEnZb"><font color="#888888" class=""><br class=""><div class="">
<div class=""><div class="">Andrew Butterfield</div><div class="">School of Computer Science & Statistics</div><div class="">Trinity College</div><div class="">Dublin 2, Ireland</div></div>
</div>
<br class=""></font></span></div></div><br class="">______________________________<wbr class="">_________________<br class="">
Haskell-Cafe mailing list<br class="">
To (un)subscribe, modify options or view archives go to:<br class="">
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe" rel="noreferrer" target="_blank" class="">http://mail.haskell.org/cgi-<wbr class="">bin/mailman/listinfo/haskell-<wbr class="">cafe</a><br class="">
Only members subscribed via the mailman list are allowed to post.<br class=""></blockquote></div><br class=""></div>
</div></blockquote></div><br class=""><div class="">
<div class=""><div class="">Andrew Butterfield</div><div class="">School of Computer Science & Statistics</div><div class="">Trinity College</div><div class="">Dublin 2, Ireland</div></div>
</div>
<br class=""></div></body></html>