<div dir="auto"><div>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"><br></div><div dir="auto">The minimum possible space complexity could well be O(1) if using String or lazy Text.</div><div dir="auto"><br></div><div dir="auto">The time complexity looks like <span style="font-family:sans-serif">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">O(min(m,n)), and that could include the cost of loading the strings too.</span></div><div dir="auto"><div class="gmail_extra" dir="auto"><br><div class="gmail_quote">On 22 Mar 2017 18:32, "Michael Litchard" <<a href="mailto:litchard.michael@gmail.com" target="_blank">litchard.michael@gmail.com</a>> wrote:<br type="attribution"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div class="m_3781259659987824222m_4002822050704418726gmail-post-text">
<p>Problem spec from <a rel="nofollow noreferrer" href="https://careercup.com/question?id=5092486548553728" target="_blank">CareerCup</a>.</p>
<p>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>-True</p>
<p>xyz,xz</p>
<p>xyz,xyk</p>
<p>xy,xyz</p>
<p>-False</p>
<p>xyz,xyz</p>
<p>xyz,xzy</p>
<p>x,xyz</p>
<pre class="m_3781259659987824222m_4002822050704418726gmail-lang-hs m_3781259659987824222m_4002822050704418726gmail-prettyprint m_3781259659987824222m_4002822050704418726gmail-prettyprinted"><code><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>So, I used <code>Text</code> instead of <code>String</code>, hoping I could take advantage of fusion. I have the following questions and my initial attempt to answer them.</p>
<p>What is the time complexity of <code>oneLetter</code>
0(m+n) where m is the length of <code>s1</code> and n is the length of <code>s2</code></p>
<p>what is the space complexity of <code>oneLetter</code>?
I'm thinking due to laziness it's O(1), only two <code>Char</code>s are in memory at any one time, or two <code>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>I don't think I can improve the time complexity. Am I right? Can the space complexity be improved?<br></p><p>What if I changed from <code>Text</code> to <code>String</code>?
I don't think the time complexity changes, but how does this change the space complexity?</p><p><br></p><p><br></p>
</div></div>
<br>______________________________<wbr>_________________<br>
Haskell-Cafe mailing list<br>
To (un)subscribe, modify options or view archives go to:<br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-bi<wbr>n/mailman/listinfo/haskell-caf<wbr>e</a><br>
Only members subscribed via the mailman list are allowed to post<br></blockquote></div></div>
</div></div>