TIC
The Interns Company

Word Break

MediumAcceptance: 48.0%
Hash TableStringDynamic ProgrammingTrieMemoization

Problem Statement

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.

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

Input Format:

  • A string s
  • An array of strings wordDict

Output Format:

  • Return true if s can be segmented into a sequence of dictionary words, otherwise false

Examples:

Example 1:

Input:

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

Output:

true

Explanation:

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

Example 2:

Input:

s = "applepenapple", wordDict = ["apple", "pen"]

Output:

true

Explanation:

Return true because "applepenapple" can be segmented as "apple pen apple". Note that you are allowed to reuse a dictionary word.

Example 3:

Input:

s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]

Output:

false

Explanation:

The string cannot be segmented into a sequence of dictionary words.

Solutions

Dynamic Programming (Bottom-Up)

Time: O(n * m) where n is the length of s and m is the length of wordDict
Space: O(n)

Use a boolean array to track whether each prefix of the string can be segmented into dictionary words.

Recursion with Memoization (Top-Down)

Time: O(n²) where n is the length of s
Space: O(n) for the memoization array

Use recursion with memoization to check if the string can be segmented.

Algorithm Walkthrough

Example input:

Step-by-step execution:

  1. s = "leetcode", wordDict = ["leet", "code"]
  2. dp[0] = true (empty string)
  3. i=1: s[0:1]="l", not in wordDict, dp[1]=false
  4. i=2: s[0:2]="le", not in wordDict, dp[2]=false
  5. i=3: s[0:3]="lee", not in wordDict, dp[3]=false
  6. i=4: s[0:4]="leet", in wordDict, dp[0]=true, dp[4]=true
  7. i=5: s[0:5]="leetc", not in wordDict, dp[5]=false
  8. i=6: s[0:6]="leetco", not in wordDict, dp[6]=false
  9. i=7: s[0:7]="leetcod", not in wordDict, dp[7]=false
  10. i=8: s[0:8]="leetcode", not in wordDict, but check s[4:8]="code" in wordDict and dp[4]=true, so dp[8]=true
  11. Return dp[8] = true

Hints

Hint 1
Consider using dynamic programming.
Hint 2
For each position in the string, check if it's possible to segment the substring up to that position.
Hint 3
Use memoization to avoid redundant calculations in recursion.

Video Tutorial

Word Break - Dynamic Programming

YouTube•Learn the Word Break solution step-by-step

Video tutorials can be a great way to understand algorithms visually

Visualization

Visualize the dynamic programming table and how subproblems are solved.

Key visualization elements:

  • current substring
  • dictionary match
  • true/false values

Asked By

AmazonFacebookGoogleMicrosoftBloombergUber

Implementation Notes

This is a classic dynamic programming problem that demonstrates both bottom-up and top-down approaches with memoization.