title: Alibaba interview: print a sentence with min spaces
body: <p>I saw this interview question and gave a go. I got stuck. The interview question is:</p>
  <blockquote>
  <p>Given a string</p>
  <pre><code>var s = &quot;ilikealibaba&quot;;
  </code></pre>
  <p>and a dictionary</p>
  <pre><code>var d = [&quot;i&quot;, &quot;like&quot;, &quot;ali&quot;, &quot;liba&quot;, &quot;baba&quot;, &quot;alibaba&quot;];
  </code></pre>
  <p>try to give the s with min space</p>
  <p>The output may be</p>
  <ol>
  <li>i like alibaba (2 spaces)</li>
  <li>i like ali baba (3 spaces)</li>
  </ol>
  <p>but pick no.1</p>
  </blockquote>
  <p>I have some code, but got stuck in the printing.
  If you have better way to do this question, let me know.</p>
  <pre><code>function isStartSub(part, s) {
    var condi = s.startsWith(part);
    return condi;
  }
  
  function getRestStr(part, s) {
    var len = part.length;
    var len1 = s.length;
    var out = s.substring(len, len1);
    return out;
  }
  
  function recPrint(arr) {
      if(arr.length == 0) {
          return '';
      } else {
          var str = arr.pop();
          return str + recPrint(arr);
      }
  
  }
  
  // NOTE: have trouble to print
  // Or if you have better ways to do this interview question, please let me know
  function myPrint(arr) {
      return recPrint(arr);
  }
  
  function getMinArr(arr) {
      var min = Number.MAX_SAFE_INTEGER;
      var index = 0;
      for(var i=0; i&lt;arr.length; i++) {
          var sub = arr[i];
          if(sub.length &lt; min) {
              min = sub.length;
              index = i;
          } else {
  
          }   
      }
  
      return arr[index];  
  }
  
  function rec(s, d, buf) {
      // Base
      if(s.length == 0) {
          return;
      } else {
      
      } 
  
      for(var i=0; i&lt;d.length; i++) {
          var subBuf = [];
  
          // baba
          var part = d[i];
          var condi = isStartSub(part, s);
  
          if(condi) {
              // rest string  
        var restStr = getRestStr(part, s);
        rec(restStr, d, subBuf);
              subBuf.unshift(part);
              buf.unshift(subBuf);
          } else {
  
          }       
      } // end loop
  
  }
  
  function myfunc(s, d) {
      var buf = [];
      rec(s, d, buf);
  
      console.log('-- test --');
      console.dir(buf, {depth:null});
  
      return myPrint(buf);    
  }
  
  
  // Output will be
  // 1. i like alibaba (with 2 spaces)
  // 2. i like ali baba (with 3 spaces)
  // we pick no.1, as it needs less spaces
  var s = &quot;ilikealibaba&quot;;
  var d = [&quot;i&quot;, &quot;like&quot;, &quot;ali&quot;, &quot;liba&quot;, &quot;baba&quot;, &quot;alibaba&quot;];
  var out = myfunc(s, d);
  console.log(out);
  </code></pre>
  <p>Basically, my output is, not sure how to print it....</p>
  <pre><code>[ [ 'i', [ 'like', [ 'alibaba' ], [ 'ali', [ 'baba' ] ] ] ] ]
  </code></pre>