⚠️ This visualization was AI-generated and may contain inaccuracies. Please verify against the original LeetCode problem (#139) before relying on it.

📝 Word Break

An interactive visualization of how dynamic programming determines if a string can be segmented into dictionary words. Watch the algorithm build up from smaller substrings to find valid word breaks.

Dynamic Programming LeetCode 139 ↗ Medium

The Problem

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

Note: The same word in the dictionary may be reused multiple times in the segmentation.

For example, given s = "leetcode" and wordDict = ["leet", "code"], return true because "leetcode" can be segmented as "leet code".

Interactive Visualization

String

Dictionary (comma-separated)

Preset

Speed:

String Segmentation

Position i: —

Checking: —

Dictionary

Status

Press Step or Play to begin.

Code

fun wordBreak(s: String, wordDict: Set<String>): Boolean {    val n = s.length    val dp = BooleanArray(n + 1)    dp[0] = true  // empty string    for (i in 1..n) {        for (j in 0 until i) {            if (dp[j] && s.substring(j, i) in wordDict) {                dp[i] = true                break            }        }    }    return dp[n]}

def wordBreak(s, wordDict):    n = len(s)    dp = [False] * (n + 1)    dp[0] = True  # empty string    for i in range(1, n + 1):        for j in range(i):            if dp[j] and s[j:i] in wordDict:                dp[i] = True                break    return dp[n]

How It Works

Key Insight

The Word Break problem uses dynamic programming to build up a solution from smaller subproblems. We define dp[i] as true if the substring s[0:i] (first i characters) can be segmented into dictionary words.

The Algorithm

Base case: dp[0] = True — an empty string can always be segmented.
For each position i from 1 to n: Check all possible split points j where 0 ≤ j < i.
Check if valid split: If dp[j] is true (meaning s[0:j] can be segmented) AND s[j:i] is in the dictionary, then dp[i] = True.
Return: dp[n] tells us if the entire string can be segmented.

Recurrence Relation

dp[i] = dp[j] AND (s[j:i] in wordDict) for any j in [0, i)

Complexity

Time O(n² × m)

Space O(n)

Where n is the length of the string and m is the average cost of dictionary lookup. With a hash set for the dictionary, m is O(1) on average, giving O(n²) time. We use O(n) space for the dp array. The nested loops check all possible substrings, leading to O(n²) substring checks.