Word Break
Problem
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.
s = "leetcode", wordDict = ["leet", "code"]truedef word_break(s, word_dict):
words = set(word_dict)
n = len(s)
dp = [False] * (n + 1)
dp[0] = True
for i in range(1, n + 1):
for j in range(i):
if dp[j] and s[j:i] in words:
dp[i] = True
break
return dp[n]function wordBreak(s, wordDict) {
const words = new Set(wordDict);
const n = s.length;
const dp = new Array(n + 1).fill(false);
dp[0] = true;
for (let i = 1; i <= n; i++) {
for (let j = 0; j < i; j++) {
if (dp[j] && words.has(s.slice(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[n];
}class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
Set<String> words = new HashSet<>(wordDict);
int n = s.length();
boolean[] dp = new boolean[n + 1];
dp[0] = true;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < i; j++) {
if (dp[j] && words.contains(s.substring(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[n];
}
}bool wordBreak(string s, vector<string>& wordDict) {
unordered_set<string> words(wordDict.begin(), wordDict.end());
int n = s.size();
vector<bool> dp(n + 1, false);
dp[0] = true;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < i; j++) {
if (dp[j] && words.count(s.substr(j, i - j))) {
dp[i] = true; break;
}
}
}
return dp[n];
}Explanation
We want to know if s can be cut into pieces that are all dictionary words. We use a boolean array dp where dp[i] means "the first i characters of s can be fully segmented".
The base case is dp[0] = true: an empty prefix is trivially segmentable. We also put the dictionary into a set so word lookups are instant.
For each position i, we look for a split point j before it. If the prefix up to j is already segmentable (dp[j] is true) and the chunk s[j..i) is a dictionary word, then the prefix up to i works too, so we set dp[i] = true and stop searching.
The final answer is dp[n] — whether the whole string can be split.
Example: s = "leetcode", dict ["leet", "code"]. dp[4] becomes true because "leet" matches from the start, then dp[8] becomes true because dp[4] is true and "code" fills the rest → answer true.