140. Word Break II

https://leetcode.com/problems/word-break-ii/

Python

DP

from functools import lru_cache


class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:

        @lru_cache(maxsize=None)
        def dp(i):
            result = []
            for word in wordDict:
                if word != s[i:i+len(word)]:
                    continue

                if len(word) == len(s)-i:
                    result.append(word)
                else:
                    for sentence in dp(i+len(word)):
                        result.append(word + ' ' + sentence)
            return result

        return dp(0)

Javascript

 var wordBreak = function(s, wordDict) {
   const result = [];
   const backtrack = function(start, record = []) {
     if (s === record.join('')) {
       const str = record.join(' ');
       if (!result.includes(str)) result.push(record.join(' '))
       return;
     }

     for (let i = start; i < s.length; i++) {
       const partial = s.slice(i);
       for (const word of wordDict) {
        if (partial.startsWith(word)) {
          record.push(word);
          // console.log(partial)
          backtrack(start + word.length, record);
          record.pop();
        }
       }
     }
   }
   backtrack(0)
   return result;
};