Word Break

Medium

Problem

Given a string s and a dictionary of words, return true if s can be split into a sequence of one or more dictionary words. Each word can be used any number of times.

Example 1

Input:  s = "leetcode", dict = ["leet", "code"]
Output: true

Example 2

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

Also asked as: Word break Problem · Word Break Problem using Backtracking

Test cases

Case 1

Input:    "leetcode", ["leet","code"]
Expected: true

Case 2

Input:    "applepenapple", ["apple","pen"]
Expected: true

Case 3

Input:    "catsandog", ["cats","dog","sand","and","cat"]
Expected: false

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. DP over prefixes

Time O(n² · L)Space O(n)

dp[i] = can s[0..i) be segmented. dp[i] is true if some j<i has dp[j] true and s[j..i) is in the dictionary.

function wordBreak(s, wordDict) {
const dict = new Set(wordDict);
const dp = Array(s.length + 1).fill(false);
dp[0] = true;
for (let i = 1; i <= s.length; i++) {
for (let j = i - 1; j >= 0; j--) {
if (dp[j] && dict.has(s.slice(j, i))) { dp[i] = true; break; }
}
}
return dp[s.length];
}