rendezvous with cassidoo #183 - Interview question of the week

makeSentence.js

/**
 * From: https://buttondown.email/cassidoo/archive/to-know-how-much-there-is-to-know-is-the/
 * @param {string} str String
 * @param {string[]} dict A list of non-empty words
 * @returns {string[]} Return all possible sentences
 * @example
 * const str = "penpineapplepenapple"
 * const dict = ["apple", "pen", "applepen", "pine", "pineapple"]
 * 
 * $ makeSentence(str, dict)
 * -> [
 *      "pen pine apple pen apple",
 *      "pen pineapple pen apple",
 *      "pen pine applepen apple"
 *    ]
 */
function makeSentence(str, dict) {
    let sentences = [""]
    for (let i = 0; i < sentences.length;) {
        const sentence = sentences[i]
        const flat = sentence.replaceAll(" ", "")
        let j = 0
        for (let item of dict)
            if (str.startsWith(flat + item)) {
                sentences[i + j] = sentence + (sentence.length > 0 ? " " : "") + item
                while (i + j in sentences) j++
            }
        if (j === 0) i++
    }
    return sentences
}