Diwali Offer!Flat 20% OFF
Enroll Now
PrakalpanaLive online tech training

169. Word Break

MediumDay 49 of 60Dynamic Programming

Given a string s and a list of words wordDict, return true if s can be split into a sequence of one or more dictionary words (with no characters left over). The same word may be used any number of times.

Example 1
Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
"leetcode" = "leet" + "code".
Example 2
Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: false
Every split leaves "og" or another piece that is not a word.
Constraints
  • 1 <= s.length <= 300
  • 1 <= wordDict.length <= 1000
  • 1 <= wordDict[i].length <= 20
  • All strings are lowercase English letters
  • Words in wordDict are unique
Hints
Frequently asked at: Amazon, Meta, Google, Microsoft, Apple
Ctrl + Enter runs the examples

Not sure what to learn next?

A 1-on-1 session with an industry mentor and a roadmap built for you. How it works

  1. 1Discuss your goals
  2. 2Get a personal plan
  3. 3Start learning
Book for β‚Ή200/ 30 min