Q96: Word Break. - DSA Patterns (Multi-Lang)

In Simple Words: 1D DP array of size $N + 1$ initialized to false, with dp[N] = true. For each index $i$ working backwards, if wordDict contains s[i : i + len(w)] and dp[i + len(w)] is true, set dp[i] = true.

Time: $O(N \cdot M \cdot K)$ | Space: $O(N)$

Multi-Language SolutionsPython 3 • JavaScript • TypeScript • Java • C++

Switch tabs or choose All

def wordBreak(s: str, wordDict: list[str]) -> bool:
    dp = [False] * (len(s) + 1)
    dp[len(s)] = True
    for i in range(len(s) - 1, -1, -1):
        for w in wordDict:
            if (i + len(w)) <= len(s) and s[i : i + len(w)] == w:
                dp[i] = dp[i + len(w)]
            if dp[i]:
                break
    return dp[0]