Word Break

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

# Solution

Let nn be the length of the string s, and mm be the number of words in wordDict.

# Vanilla DFS (TLE)

Complexity

time: O(nm)O(n^m)
space: O(n)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)
1
2
3
4
5
6
7
8
9
10
11
12
13
14

# Memoized DFS

Complexity

time: O(nm)O(nm)
space: O(n)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)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19