Problem statement

https://binarysearch.com/problems/Break-String-Into-Words/

Solution

Equal to leetcode 0139. Word Break

Complexity

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

Code

class Solution:
    def solve(self, wordDict, s):
        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)