Introduction

Word Break is one of the most important String Dynamic Programming interview questions.

You are given:

string swordDict[]

Goal:

Determine whether the string can be segmented into one or more dictionary words.

Example

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

Output:

true

Explanation:

"leet" + "code"

Key Observation

At every position:

Try breaking the string at every possible index.

DP State:

dp[i] = Can substrings[0...i-1] be segmented?

Transition:

dp[i] = trueif dp[j] == true
and s[j:i] exists in dictionary

Dry Run

Input:

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

DP:

dp[0] = truedp[4] = true
dp[8] = true

Answer:

true

Approach 1 : Memoization

Explanation

For every position:

  1. Try all partitions.
  2. Check dictionary word.
  3. Recurse on remaining string.
  4. Store answer.
  5. Reuse computations.

Approach 2 : Tabulation

Explanation

State:

dp[i]

Meaning:

Can first i characters form valid words?

Transition:

If dp[j] is trueand s[j:i] exists in dictionary
then
dp[i] = true

Practice

Complexity Analysis

MemoizationTime Complexity: O(n²)
Space Complexity: O(n)

Tabulation
Time Complexity: O(n²)
Space Complexity: O(n)

Why This Problem is Important

  • String DP
  • Partition DP
  • Boolean DP
  • Dictionary Lookup
  • State Design

Common Beginner Mistakes

  • Forgetting dp[0] = true
  • Using list instead of set
  • Wrong substring boundaries
  • Missing break statement
  • Incorrect state definition

Interview Tip

Always explain:

dp[i] = Can first i characters be segmented?

Then:

Try every partition point.

This is the key insight interviewers expect.

Related Questions

  • Palindromic Substrings
  • Longest Palindromic Subsequence
  • Partition Equal Subset Sum
  • Decode Ways
  • Concatenated Words

Final Takeaway

Word Break is one of the most important String Dynamic Programming problems.

It teaches:

  • Partition DP
  • Boolean DP
  • String Segmentation
  • State Transitions

Mastering Word Break makes many advanced string segmentation and partition DP interview questions significantly easier.