javascript - Alibaba intervju: skriv ut en mening med minsta antal mellanslag
Jag såg denna intervjufråga och försökte svara. Jag fastnade. Intervjufrågan är:
Givet en sträng
var s = "ilikealibaba";och en ordbok
var d = ["i", "like", "ali", "liba", "baba", "alibaba"];försök att ge s med minimal plats
Utgången kan vara
- jag gillar alibaba
- jag gillar ali baba
men välj nr 1
Jag har lite kod, men fastnade i utskriften. Om du har ett bättre sätt att göra denna fråga, låt mig veta.
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 princip är min output, är inte säker på hur jag ska skriva ut den....
[ [ 'i', [ 'like', [ 'alibaba' ], [ 'ali', [ 'baba' ] ] ] ] ]
Svar #1
Detta problem lämpar sig bäst för en dynamisk programmeringsmetod. Delproblemet är, "vad är det bästa sättet att skapa ett prefix av s". Sedan, för ett givet prefix av s, överväger vi alla ord som matchar slutet av prefixet, och väljer det bästa med hjälp av resultaten från de tidigare prefixen.
Här är en 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]);Svar #2
pkpnds svar är på rätt spår. Men ordböcker tenderar att vara ganska stora uppsättningar, och att iterera över hela ordboken vid varje tecken i strängen kommer att vara ineffektivt. (Att dessutom spara hela sekvensen för varje dp-cell kan konsumera mycket utrymme.) Istället kan vi formulera frågan, medan vi itererar över strängen, som: givet alla tidigare index i strängen som hade ordboksmatchningar som sträckte sig bakåt (antingen till början eller till en annan matchning), vilken är både en ordboksmatch när vi inkluderar det nuvarande tecknet, och har en mindre total längd. Generellt:
f(i) = min(
f(j) + length(i - j) + (1 if j is after the start of the string)
)
for all j < i, where string[j] ended a dictionary match
and string[j+1..i] is in the dictionary
Eftersom vi endast lägger till ytterligare en j när det finns en matchning och en ny matchning bara kan sträcka sig tillbaka till en tidigare matchning eller till början av strängen, kan vår datastruktur vara en array av tupler, (bästa index som denna match sträcker sig tillbaka till, total längd hittills). Vi lägger till en ny tuppel om det nuvarande tecknet kan förlänga en ordlista-matchning tillbaka till en annan post vi redan har. Vi kan också optimera genom att avsluta tidigt från den bakåtgående sökningen när den matchade delsträngen skulle vara längre än det längsta ordet i ordlistan, och bygga delsträngen att jämföra mot ordlistan medan vi itererar bakåt.
JavaScript-kod:
function f(str, dict){
let m = [[-1, -1, -1]];
for (let i=0; i<str.length; i++){
let best = [null, null, Infinity];
let substr = '';
let _i = i;
for (let j=m.length-1; j>=0; j--){
let [idx, _j, _total] = m[j];
substr = str.substr(idx + 1, _i - idx) + substr;
_i = idx;
if (dict.has(substr)){
let total = _total + 1 + i - idx;
if (total < best[2])
best = [i, j, total];
}
}
if (best[0] !== null)
m.push(best);
}
return m;
}
var s = "ilikealibaba";
var d = new Set(["i", "like", "ali", "liba", "baba", "alibaba"]);
console.log(JSON.stringify(f(s,d)));Vi kan spåra tillbaka vårt resultat:
[[-1,-1,-1],[0,0,1],[4,1,6],[7,2,10],[11,2,14]]
[11, 2, 14] means a total length of 14,
where the previous index in m is 2 and the right index
of the substr is 11
=> follow it back to m[2] = [4, 1, 6]
this substr ended at index 4 (which means the
first was "alibaba"), and followed m[1]
=> [0, 0, 1], means this substr ended at index 1
so the previous one was "like"
Och där har du det: "jag gillar Alibaba"