title: Breaking a string apart into a sequence of words
body: <p>I recently came across the following interview question:</p>
  
  <blockquote>
    <p>Given an input string and a dictionary of words, implement a method that breaks up the input string into a space-separated string of dictionary words that a search engine might use for "Did you mean?" For example, an input of "applepie" should yield an output of "apple pie".</p>
  </blockquote>
  
  <p>I can't seem to get an optimal solution as far as complexity is concerned.  Does anyone have any suggestions on how to do this efficiently?</p>