MediumDynamic Programming

Word Break

Explanation & Solution

Description

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 that the same word in the dictionary may be reused multiple times in the segmentation.

Input:s = "leetcode", wordDict = ["leet","code"]

leet

code

Output: true

Explanation: Return true because "leetcode" can be segmented as "leet code".

Constraints

1 <= s.length <= 300
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 20
s and wordDict[i] consist of only lowercase English letters
All the strings of wordDict are unique

Approach

Dynamic Programming pattern

1. Create a Word Set

Convert wordDict into a Set for O(1) lookups
This avoids scanning the entire dictionary array for each substring check

2. Define the DP Array

Create a boolean array dp of size s.length + 1, initialized to false
dp[i] represents whether the substring s[0..i-1] (the first i characters) can be segmented into dictionary words
Set dp[0] = true because the empty string is trivially segmentable

3. Fill the DP Table

For each position i from 1 to s.length:
Check every split point j from 0 to i - 1
If dp[j] is true (meaning s[0..j-1] can be segmented) and s[j..i-1] is a word in the dictionary, then set dp[i] = true
Once we find a valid split, break early since we only need one valid segmentation

4. Return the Result

dp[s.length] tells us whether the entire string can be segmented
Return dp[s.length]

Key Insight

The problem has optimal substructure: if s[0..j-1] can be segmented and s[j..i-1] is a valid word, then s[0..i-1] can be segmented
Using a Set for the dictionary makes word lookups constant time

Time

O(n^2 * m) where n is the length of the string and m is the average length of substring comparison (substring creation)

Space

O(n) for the DP array plus O(k) for the word set where k is the total characters in the dictionary

Visualization

Input:

Dynamic Programmings = "leetcode", wordDict = ["leet","code"]

Press play to start DP animation

ComputingDependencyFilledEmpty

10 steps

Solution Code

Longest Increasing Subsequence

Longest Common Subsequence