<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="">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>I guess the above should be O(1) in space - it's just a list crawl with tests</div><div>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><blockquote type="cite" class=""><div class="">On 22 Mar 2017, at 18:48, 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="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><br class=""></div></div><div><blockquote type="cite" class=""><div class=""><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_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_3781259659987824222m_4002822050704418726gmail-prettyprint m_3781259659987824222m_4002822050704418726gmail-lang-hs m_3781259659987824222m_4002822050704418726gmail-prettyprinted"><code class=""><span class="m_3781259659987824222m_4002822050704418726gmail-kwd">module</span><span class="m_3781259659987824222m_4002822050704418726gmail-pln"> Strings.OneLetter </span><span class="m_3781259659987824222m_4002822050704418726gmail-kwd">where</span><span class="m_3781259659987824222m_4002822050704418726gmail-pun">`</span><span class="m_3781259659987824222m_4002822050704418726gmail-pln">
</span><span class="m_3781259659987824222m_4002822050704418726gmail-kwd">import</span><span class="m_3781259659987824222m_4002822050704418726gmail-pln"> Prelude
</span><span class="m_3781259659987824222m_4002822050704418726gmail-kwd">import</span><span class="m_3781259659987824222m_4002822050704418726gmail-pln"> qualified Data.Text as T</span><span class="m_3781259659987824222m_4002822050704418726gmail-pun">`</span><span class="m_3781259659987824222m_4002822050704418726gmail-pln">
oneLetter </span><span class="m_3781259659987824222m_4002822050704418726gmail-pun">::</span><span class="m_3781259659987824222m_4002822050704418726gmail-pln"> T.Text </span><span class="m_3781259659987824222m_4002822050704418726gmail-pun">-></span><span class="m_3781259659987824222m_4002822050704418726gmail-pln"> T.Text </span><span class="m_3781259659987824222m_4002822050704418726gmail-pun">-></span><span class="m_3781259659987824222m_4002822050704418726gmail-pln"> Bool
oneLetter s1 s2
</span><span class="m_3781259659987824222m_4002822050704418726gmail-pun">|</span><span class="m_3781259659987824222m_4002822050704418726gmail-pln"> s1 </span><span class="m_3781259659987824222m_4002822050704418726gmail-pun">==</span><span class="m_3781259659987824222m_4002822050704418726gmail-pln"> s2 </span><span class="m_3781259659987824222m_4002822050704418726gmail-pun">=</span><span class="m_3781259659987824222m_4002822050704418726gmail-pln"> False
</span><span class="m_3781259659987824222m_4002822050704418726gmail-pun">|</span><span class="m_3781259659987824222m_4002822050704418726gmail-pln"> max_l </span><span class="m_3781259659987824222m_4002822050704418726gmail-pun">></span><span class="m_3781259659987824222m_4002822050704418726gmail-pln"> </span><span class="m_3781259659987824222m_4002822050704418726gmail-pun">(</span><span class="m_3781259659987824222m_4002822050704418726gmail-pln">min_l </span><span class="m_3781259659987824222m_4002822050704418726gmail-pun">+</span><span class="m_3781259659987824222m_4002822050704418726gmail-pln"> </span><span class="m_3781259659987824222m_4002822050704418726gmail-lit">1</span><span class="m_3781259659987824222m_4002822050704418726gmail-pun">)</span><span class="m_3781259659987824222m_4002822050704418726gmail-pln"> </span><span class="m_3781259659987824222m_4002822050704418726gmail-pun">=</span><span class="m_3781259659987824222m_4002822050704418726gmail-pln"> False
</span><span class="m_3781259659987824222m_4002822050704418726gmail-pun">|</span><span class="m_3781259659987824222m_4002822050704418726gmail-pln"> max_l </span><span class="m_3781259659987824222m_4002822050704418726gmail-pun">==</span><span class="m_3781259659987824222m_4002822050704418726gmail-pln"> min_l </span><span class="m_3781259659987824222m_4002822050704418726gmail-pun">=</span><span class="m_3781259659987824222m_4002822050704418726gmail-pln"> diff_size </span><span class="m_3781259659987824222m_4002822050704418726gmail-pun">==</span><span class="m_3781259659987824222m_4002822050704418726gmail-pln"> </span><span class="m_3781259659987824222m_4002822050704418726gmail-lit">1</span><span class="m_3781259659987824222m_4002822050704418726gmail-pln">
</span><span class="m_3781259659987824222m_4002822050704418726gmail-pun">|</span><span class="m_3781259659987824222m_4002822050704418726gmail-pln"> otherwise </span><span class="m_3781259659987824222m_4002822050704418726gmail-pun">=</span><span class="m_3781259659987824222m_4002822050704418726gmail-pln"> diff_size </span><span class="m_3781259659987824222m_4002822050704418726gmail-pun">==</span><span class="m_3781259659987824222m_4002822050704418726gmail-pln"> </span><span class="m_3781259659987824222m_4002822050704418726gmail-lit">0</span><span class="m_3781259659987824222m_4002822050704418726gmail-pln">
</span><span class="m_3781259659987824222m_4002822050704418726gmail-kwd">where</span><span class="m_3781259659987824222m_4002822050704418726gmail-pln">
length_s1 </span><span class="m_3781259659987824222m_4002822050704418726gmail-pun">=</span><span class="m_3781259659987824222m_4002822050704418726gmail-pln"> T.length s1
length_s2 </span><span class="m_3781259659987824222m_4002822050704418726gmail-pun">=</span><span class="m_3781259659987824222m_4002822050704418726gmail-pln"> T.length s2
max_l </span><span class="m_3781259659987824222m_4002822050704418726gmail-pun">=</span><span class="m_3781259659987824222m_4002822050704418726gmail-pln"> max length_s1 length_s2
min_l </span><span class="m_3781259659987824222m_4002822050704418726gmail-pun">=</span><span class="m_3781259659987824222m_4002822050704418726gmail-pln"> min length_s1 length_s2
diff_size </span><span class="m_3781259659987824222m_4002822050704418726gmail-pun">=</span><span class="m_3781259659987824222m_4002822050704418726gmail-pln"> length </span><span class="m_3781259659987824222m_4002822050704418726gmail-pun">$</span><span class="m_3781259659987824222m_4002822050704418726gmail-pln"> filter </span><span class="m_3781259659987824222m_4002822050704418726gmail-pun">(\(</span><span class="m_3781259659987824222m_4002822050704418726gmail-pln">a</span><span class="m_3781259659987824222m_4002822050704418726gmail-pun">,</span><span class="m_3781259659987824222m_4002822050704418726gmail-pln">b</span><span class="m_3781259659987824222m_4002822050704418726gmail-pun">)</span><span class="m_3781259659987824222m_4002822050704418726gmail-pln"> </span><span class="m_3781259659987824222m_4002822050704418726gmail-pun">-></span><span class="m_3781259659987824222m_4002822050704418726gmail-pln"> a </span><span class="m_3781259659987824222m_4002822050704418726gmail-pun">/=</span><span class="m_3781259659987824222m_4002822050704418726gmail-pln"> b</span><span class="m_3781259659987824222m_4002822050704418726gmail-pun">)</span><span class="m_3781259659987824222m_4002822050704418726gmail-pln"> zipped
zipped </span><span class="m_3781259659987824222m_4002822050704418726gmail-pun">=</span><span class="m_3781259659987824222m_4002822050704418726gmail-pln"> T.zip s1 s2</span><span class="m_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>
_______________________________________________<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" class="">http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe</a><br class="">Only members subscribed via the mailman list are allowed to post.</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>