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

Let dfs(k) be a possibility to split string s[k:] into words from wordSet. Then to check if word s[k:] can be splitted, we need to check if for some i word s[k:i] in our wordSet and if s[i:] can be splitted, which is dfs(i).

Complexity: let T be the maximum length of word in our wordSet. Then we need O(T) time to check if word in our set, so we have overall O(n^2T) complexity. Space complexity is O(n +Tn) : to keep our cache and to keep our set of wordSet

class Solution:
    def wordBreak(self, s, wordDict):
        wordSet = set(wordDict)
        n = len(s)
   
        @lru_cache(None)
        def dfs(k):
            if k == n: return True
            for i in range(k + 1, n + 1):
                if s[k:i] in wordSet and dfs(i):
                    return True        
            return False
        
        return dfs(0)

Further discussion: Another approach is to use KMP for each of the m words and create n x n table Mem, where Mem[i][j] is equal to 1 if s[i:j] is in our dictionary. The complexity to generate Mem table is O(mn) and O(n^2) to update dp. Finally, we have O(n^2 + nm) time and O(n^2) memory.

One more approach is to use Tries to preprocess our dictionary with O(mk) time, where k is the average length of words. Then we can fill dp table in O(n^2) time (CHECK, I am not 100 percent sure). Finally, we have O(mk + n^2) time and O(mk) memory.

If you like the solution, you can upvote it on leetcode discussion section: Problem 0139