Word Break — Medium Coding Interview Question

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.

Example

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

Output: true

Constraints

• 1 ≤ s.length ≤ 300
• 1 ≤ wordDict.length ≤ 1000

Topics & Companies

Topics: dp, hash-map

Asked by: Amazon, Google, Meta, Microsoft, Apple, Bloomberg

Optimal Solution Complexity

Time complexity: O(n²). Space complexity: O(n).

Practice more

• All DSA Problems
• DSA Patterns