Alibaba interview: print a sentence with min spaces

  • A+
Category:Languages

I saw this interview question and gave a go. I got stuck. The interview question is:

Given a string

var s = "ilikealibaba"; 

and a dictionary

var d = ["i", "like", "ali", "liba", "baba", "alibaba"]; 

try to give the s with min space

The output may be

  1. i like alibaba (2 spaces)
  2. i like ali baba (3 spaces)

but pick no.1

I have some code, but got stuck in the printing. If you have better way to do this question, let me know.

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<arr.length; i++) {         var sub = arr[i];         if(sub.length < 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<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 = "ilikealibaba"; var d = ["i", "like", "ali", "liba", "baba", "alibaba"]; var out = myfunc(s, d); console.log(out); 

Basically, my output is, not sure how to print it....

[ [ 'i', [ 'like', [ 'alibaba' ], [ 'ali', [ 'baba' ] ] ] ] ] 


This problem is best suited for a dynamic programming approach. The subproblem is, "what is the best way to create a prefix of s". Then, for a given prefix of s, we consider all words that match the end of the prefix, and choose the best one using the results from the earlier prefixes.

Here is an implementation:

var s = "ilikealibaba"; var arr = ["i", "like", "ali", "liba", "baba", "alibaba"];  var dp = []; // dp[i] is the optimal solution for s.substring(0, i) dp.push("");  for (var i = 1; i <= s.length; i++) {     var best = null; // the best way so far for s.substring(0, i)      for (var j = 0; j < arr.length; j++) {         var word = arr[j];         // consider all words that appear at the end of the prefix         if (!s.substring(0, i).endsWith(word))             continue;          if (word.length == i) {             best = word; // using single word is optimal             break;         }          var prev = dp[i - word.length];         if (prev === null)             continue; // s.substring(i - word.length) can't be made at all          if (best === null || prev.length + word.length + 1 < best.length)             best = prev + " " + word;     }     dp.push(best); }  console.log(dp[s.length]);

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: