#108 Medium Time O(n³) Space O(n) Animated

Word Break

Determine if string can be segmented using dictionary words.

LeetCode ↗

Approach: Dynamic Programming (1D)

Click play to start

Step 0 / 0

Press play to start the visualization.

1×

Description

Determine if string can be segmented using dictionary words.

Constraints

Time Complexity: O(n³)
Space Complexity: O(n)

Solution — Dynamic Programming (1D)

O(n³) O(n)

def wordBreak(s, wordDict):
    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]

Maximum Product Subarray

Longest Increasing Subsequence

Word Break

Steps

Description

Constraints

Tags

Solution — Dynamic Programming (1D)