Word Break

Solution

Let $n$ be the length of the string s, and $m$ be the number of words in wordDict.

Vanilla DFS (TLE)

Complexity

time: $O(n^m)$
space: $O(n)$

def wordBreak(self, s: str, wordDict: List[str]) -> bool:
    def dfs(start):
        if start == len(s):
            return True
        for word in wordDict:
            n = len(word)
            if start + n > len(s):
                continue
            if s[start: start + n] != word:
                continue
            if dfs(start + n):
                return True
        return False
    return dfs(0)

Memoized DFS

Complexity

time: $O(nm)$
space: $O(n)$

def wordBreak(self, s: str, wordDict: List[str]) -> bool:
    def dfs(start):
        if start == len(s):
            return True
        if memo[start] != None:
            return memo[start]
        for word in wordDict:
            n = len(word)
            if start + n > len(s):
                continue
            if s[start: start + n] != word:
                continue
            if dfs(start + n):
                memo[start] = True
                return True
        memo[start] = False
        return False
    memo = [None for _ in range(len(s))]
    return dfs(0)