javascript - 阿里巴巴面试: print a sentence with min spaces

Question

我看到了这个面试题，试了一下。我被困。面试问题是:

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

我有一些代码，但在打印过程中卡住了。如果你有更好的方法来做这道题，请告诉我。

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

基本上，我的输出是，不确定如何打印....

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

Answer 1

这个问题最适合动态规划方法。子问题是“创建 s 前缀的最佳方法是什么”。然后，对于给定的 s 前缀，我们考虑所有匹配前缀末尾的单词，并使用前面前缀的结果选择最佳单词。

这是一个实现:

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