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

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

请您参考如下方法:

这个问题最适合动态规划方法。子问题是“创建 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]);