<div dir="ltr"><div class="gmail-post-text">

<p>Problem spec from <a rel="nofollow noreferrer" href="https://careercup.com/question?id=5092486548553728">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="gmail-lang-hs gmail-prettyprint gmail-prettyprinted"><code><span class="gmail-kwd">module</span><span class="gmail-pln"> Strings.OneLetter </span><span class="gmail-kwd">where</span><span class="gmail-pun">`</span><span class="gmail-pln">

</span><span class="gmail-kwd">import</span><span class="gmail-pln"> Prelude
</span><span class="gmail-kwd">import</span><span class="gmail-pln"> qualified Data.Text as T</span><span class="gmail-pun">`</span><span class="gmail-pln">

oneLetter </span><span class="gmail-pun">::</span><span class="gmail-pln"> T.Text </span><span class="gmail-pun">-></span><span class="gmail-pln"> T.Text </span><span class="gmail-pun">-></span><span class="gmail-pln"> Bool
oneLetter s1 s2
  </span><span class="gmail-pun">|</span><span class="gmail-pln"> s1 </span><span class="gmail-pun">==</span><span class="gmail-pln"> s2 </span><span class="gmail-pun">=</span><span class="gmail-pln"> False
  </span><span class="gmail-pun">|</span><span class="gmail-pln"> max_l </span><span class="gmail-pun">></span><span class="gmail-pln"> </span><span class="gmail-pun">(</span><span class="gmail-pln">min_l </span><span class="gmail-pun">+</span><span class="gmail-pln"> </span><span class="gmail-lit">1</span><span class="gmail-pun">)</span><span class="gmail-pln"> </span><span class="gmail-pun">=</span><span class="gmail-pln"> False
  </span><span class="gmail-pun">|</span><span class="gmail-pln"> max_l </span><span class="gmail-pun">==</span><span class="gmail-pln"> min_l </span><span class="gmail-pun">=</span><span class="gmail-pln"> diff_size </span><span class="gmail-pun">==</span><span class="gmail-pln"> </span><span class="gmail-lit">1</span><span class="gmail-pln">
  </span><span class="gmail-pun">|</span><span class="gmail-pln"> otherwise </span><span class="gmail-pun">=</span><span class="gmail-pln"> diff_size </span><span class="gmail-pun">==</span><span class="gmail-pln"> </span><span class="gmail-lit">0</span><span class="gmail-pln">
  </span><span class="gmail-kwd">where</span><span class="gmail-pln">
    length_s1 </span><span class="gmail-pun">=</span><span class="gmail-pln"> T.length s1
    length_s2 </span><span class="gmail-pun">=</span><span class="gmail-pln"> T.length s2
    max_l </span><span class="gmail-pun">=</span><span class="gmail-pln"> max length_s1 length_s2
    min_l </span><span class="gmail-pun">=</span><span class="gmail-pln"> min length_s1 length_s2
    diff_size </span><span class="gmail-pun">=</span><span class="gmail-pln"> length </span><span class="gmail-pun">$</span><span class="gmail-pln"> filter </span><span class="gmail-pun">(\(</span><span class="gmail-pln">a</span><span class="gmail-pun">,</span><span class="gmail-pln">b</span><span class="gmail-pun">)</span><span class="gmail-pln"> </span><span class="gmail-pun">-></span><span class="gmail-pln"> a </span><span class="gmail-pun">/=</span><span class="gmail-pln"> b</span><span class="gmail-pun">)</span><span class="gmail-pln"> zipped
    zipped </span><span class="gmail-pun">=</span><span class="gmail-pln"> T.zip s1 s2</span><span class="gmail-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>