Back to Problems

Word Break

Medium
dynamic-programming

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.

Recurrence Relation: dp[i] = true if there exists j < i such that dp[j] is true AND s[j..i-1] is in wordDict

dp[i] represents whether the substring s[0..i-1] can be segmented using dictionary words.

This problem combines string processing with dynamic programming and can also be solved with BFS or memoized recursion.

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 can reuse dictionary words.

Example 3

Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: false
Explanation: The string cannot be fully segmented using the dictionary words.

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.
Show Hints (4)
Hint 1: dp[i] is true if we can form the first i characters using dictionary words.
Hint 2: For each position i, check all possible word endings.
Hint 3: If dp[j] is true and s[j..i] is in the dictionary, then dp[i] is true.
Hint 4: Use a set for O(1) dictionary lookups.
Loading editor...

Test Results

Click "Run" to execute your code against test cases

AI Tutor

Socratic guidance - I'll ask questions, not give answers

AI Tutor
Hello! I'm your AI tutor, here to guide you through this problem using the Socratic method. I won't give you direct answers, but I'll ask questions and provide hints to help you discover the solution yourself. What's your first instinct when you look at this problem? What approach comes to mind?