Skip to content
BASA DSA

Word Break

Medium1-D Dynamic Programming

Return whether s can be split into one or more dictionary words. A word may be reused.

Example 1

Input
s = "campcamp"
wordDict = ["camp"]
Output
true

Explanation

Use camp twice because dictionary entries may be reused.

Example 2

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

Explanation

cats/and leaves og, absent from the dictionary; no complete split exists.

Example 3

Input
s = "abcd"
wordDict = ["a","bc","d"]
Output
true

Explanation

a/bc/d covers every character in order.

Constraints

  • 1 <= len(s) <= 300
  • Dictionary contains 1..1000 distinct nonempty lowercase words
  • s is lowercase

Function contractwordBreakArguments: json, json
Loading draft…
SolutionRuns on your device