Word Break

MediumDynamic ProgrammingDynamic Programming

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

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

Examples

Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Return true because "leetcode" can be segmented as "leet code".
Input: s = "applepenapple", wordDict = ["apple","pen"]
Output: true
Return true because "applepenapple" can be segmented as "apple pen apple".
Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: false

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.

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More Dynamic Programming problems