pinapple pen interview question

solution.js

/*
Given a string str and a dictionary dict containing a list of non-empty words, add spaces in str to construct a “sentence” where each word is a valid word in dict. Return all possible sentences. You are allowed to reuse the words in dict.

Example:
str = “penpineapplepenapple”
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){
  const findWordsAtStart = str => dict.filter(word => str.startsWith(word))
  const R = (str, sentences) => {
    const words = findWordsAtStart(str)
    if(str.length === 0 || words.length === 0) return sentences // end of recursion
    
    return words.flatMap(word => {
       const restOfStr = str.slice(word.length)
       return R(restOfStr, sentences.map(s => s ? s + " " + word : word))
    })
  }

  const sentences = [""]; // initial empty sentence
  return R(str, sentences)
}


str = "penpineapplepenapple"
dict = ["apple", "pen", "applepen", "pine", "pineapple"]
makeSentence(str, dict)