Word Break
Word Break
Given a string s and a dictionary of words, determine if s can be segmented into a space-separated sequence of one or more dictionary words. Example: s="leetcode", dict=["leet","code"] → YES ("leet" + "code") Example: s="applepenapple", dict=["apple","pen"] → YES Example: s="catsandog", dict=["cats","dog","sand","and","cat"] → NO
Input format — only if your code reads from stdin
Input format: - First line: the string s - Second line: integer n (number of words in dictionary) - Next n lines: one dictionary word per line Output: YES if s can be segmented using dictionary words, NO otherwise.
Approach
Bottom-up DP: dp[i] = true if s[0..i-1] can be segmented. dp[0] = true. For each position i from 1 to len(s), check all j < i: if dp[j] is true and s[j..i-1] is in the dictionary, set dp[i] = true.
Input
Output
- •
1 ≤ len(s) ≤ 300, 1 ≤ n ≤ 1000, dict words are lowercase English letters
More Dynamic Programming problems
Browse all coding problems →Press Run to test your custom input, or Submit to judge against all test cases.
Sign in to continue
Create a free account to run code, submit solutions and track progress.
- Free forever — no credit card
- 10+ languages with live execution
- Points, streaks & leaderboards