Интервью Alibaba: напечатать предложение с минимальными пробелами

Question

Я видел этот вопрос интервью и дал понять Я застрял. Вопрос интервью:

С учетом строки

var s = "ilikealibaba";

и словарь

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

попробуйте ввести с мин пробел

Выход может быть

1. мне нравится алибаба (2 пробела)
2. Мне нравится Али Баба (3 пробела)

но выберите № 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

pkpnd ответ по правильному пути. Но словари имеют тенденцию быть довольно большими наборами, и итерации по всему словарю для каждого символа строки будут неэффективными. (Кроме того, сохранение всей последовательности для каждой ячейки dp может занять много места.) Скорее, мы можем сформулировать вопрос, перебирая строку, следующим образом: учитывая все предыдущие индексы строки, для которых словарь соответствует расширению назад (либо к началу, либо к другому совпадению), которое является словарным совпадением, когда мы включаем текущий символ, и имеет в целом меньшую длину. В целом:

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 

Поскольку мы добавляем еще один j только при наличии совпадения, а новое совпадение может распространяться только на предыдущее совпадение или на начало строки, наша структура данных может быть массивом кортежей, (best index this match extends back to, total length up to here). Мы добавляем еще один кортеж, если текущий символ может расширить словарное совпадение до другой записи, которая у нас уже есть. Мы также можем оптимизировать, выйдя рано из поиска в обратном направлении, когда соответствующая подстрока станет больше, чем самое длинное слово в словаре, и создав подстроку для сравнения со словарем, когда мы выполняем итерацию в обратном направлении.

Код JavaScript:

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

Мы можем отследить наш результат:

[[-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"

И вот оно: «Мне нравится алибаба»

Answer 2

Использование структуры данных Trie

1. Построение структуры данных Trie на основе данных словаря
2. Поиск предложения по всем возможным фрагментам и построение дерева решений
3. Глубокий обход дерева решений и сортировка окончательных комбинаций

const sentence = 'ilikealibaba';
const words = ['i', 'like', 'ali', 'liba', 'baba', 'alibaba',];

class TrieNode {
    constructor() { }
    set(a) {
        this[a] = this[a] || new TrieNode();
        return this[a];
    }
    search(word, marks, depth = 1) {
        word = Array.isArray(word) ? word : word.split('');
        const a = word.shift();
        if (this[a]) {
            if (this[a]._) {
                marks.push(depth);
            }
            this[a].search(word, marks, depth + 1);
        } else {
            return 0;
        }
    }
}

TrieNode.createTree = words => {
    const root = new TrieNode();
    words.forEach(word => {
        let currentNode = root;
        for (let i = 0; i < word.length; i++) {
            currentNode = currentNode.set(word[i]);
        }
        currentNode.set('_');
    });
    return root;
};

const t = TrieNode.createTree(words);

function searchSentence(sentence) {
    const marks = [];
    t.search(sentence, marks);
    const ret = {};
    marks.map(mark => {
        ret[mark] = searchSentence(sentence.slice(mark));
    });
    return ret;
}

const solutionTree = searchSentence(sentence);

function deepTraverse(tree, sentence, targetLen = sentence.length) {
    const stack = [];
    const sum = () => stack.reduce((acc, mark) => acc + mark, 0);
    const ret = [];
    (function traverse(tree) {
        const keys = Object.keys(tree);
        keys.forEach(key => {
            stack.push(+key);
            if (sum() === targetLen) {
                const result = [];
                let tempStr = sentence;
                stack.forEach(mark => {
                    result.push(tempStr.slice(0, mark));
                    tempStr = tempStr.slice(mark);
                });
                ret.push(result);
            }
            if(tree[key]) {
                traverse(tree[key]);
            }
            stack.pop();
        });
    })(tree);
    return ret;
}

const solutions = deepTraverse(solutionTree, sentence);

solutions.sort((s1, s2) => s1.length - s2.length).forEach((s, i) => {
    console.log(`${i + 1}. ${s.join(' ')} (${s.length - 1} spaces)`);
});
console.log('pick no.1');

Answer 3

Эта проблема лучше всего подходит для подхода динамического программирования.Подзадача: «Каков наилучший способ создать префикс 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]);

Answer 4

Вы можете собрать все возможные комбинации строки, проверив начальную строку и отобразив результат.

Если несколько результатов имеют минимальную длину, принимаются все результаты.

Это может не работать для экстремумов со строкой, которая просто содержит одну и ту же базовую строку, как 'abcabc' и 'abc'. В этом случае я предлагаю использовать самую короткую строку и обновить любой результат детали путем итерации для нахождения более длинных строк и замены, если это возможно.

function getWords(string, array = []) {
    words
        .filter(w => string.startsWith(w))
        .forEach(s => {
            var rest = string.slice(s.length),
                temp = array.concat(s);
            if (rest) {
                getWords(rest, temp);
            } else {
                result.push(temp);
            }
        });
}


var string = "ilikealibaba",
    words = ["i", "like", "ali", "liba", "baba", "alibaba"],
    result = [];
    
getWords(string);

console.log('all possible combinations:', result);

console.log('result:', result.reduce((r, a) => {
    if (!r || r[0].length > a.length) {
        return [a];
    }
    if (r[0].length === a.length) {
        r.push(a);
    }
    return r;
}, undefined))

Answer 5

Поскольку вас попросят найти кратчайший ответ, вероятно, Поиск в ширину будет возможным решением. Или вы можете посмотреть A * Поиск .

Вот рабочий пример с A * (потому что это менее привлекательно, чем BFS :)), в основном просто скопированный из статьи в Википедии. Вся магия «превращения строки в график» происходит в функции getNeighbors

https://jsfiddle.net/yLeps4v5/4/

var str = 'ilikealibaba'
var dictionary = ['i', 'like', 'ali', 'baba', 'alibaba']

var START = -1
var FINISH = str.length - 1

// Returns all the positions in the string that we can "jump" to from position i
function getNeighbors(i) {
    const matchingWords = dictionary.filter(word => str.slice(i + 1, i + 1 + word.length) == word)
    return matchingWords.map(word => i + word.length)
}

function aStar(start, goal) {
    // The set of nodes already evaluated
    const closedSet = {};

    // The set of currently discovered nodes that are not evaluated yet.
    // Initially, only the start node is known.
    const openSet = [start];

    // For each node, which node it can most efficiently be reached from.
    // If a node can be reached from many nodes, cameFrom will eventually contain the
    // most efficient previous step.
    var cameFrom = {};

    // For each node, the cost of getting from the start node to that node.
    const gScore = dictionary.reduce((acc, word) => { acc[word] = Infinity; return acc }, {})

    // The cost of going from start to start is zero.
    gScore[start] = 0

    while (openSet.length > 0) {
        var current = openSet.shift()
        if (current == goal) {
            return reconstruct_path(cameFrom, current)
        }

        closedSet[current] = true;

        getNeighbors(current).forEach(neighbor => {
            if (closedSet[neighbor]) {
                return      // Ignore the neighbor which is already evaluated.
            }

            if (openSet.indexOf(neighbor) == -1) {  // Discover a new node
                openSet.push(neighbor)
            }

            // The distance from start to a neighbor
            var tentative_gScore = gScore[current] + 1
            if (tentative_gScore >= gScore[neighbor]) {
                return      // This is not a better path.
            }

            // This path is the best until now. Record it!
            cameFrom[neighbor] = current
            gScore[neighbor] = tentative_gScore
        })
    }

    throw new Error('path not found')
}

function reconstruct_path(cameFrom, current) {
    var answer = [];
    while (cameFrom[current] || cameFrom[current] == 0) {
        answer.push(str.slice(cameFrom[current] + 1, current + 1))
        current = cameFrom[current];
    }
    return answer.reverse()
}

console.log(aStar(START, FINISH));