Alibaba interview: print a sentence with min spaces

Question

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' ] ] ] ] ]

Answer 1

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]);