Can a String Be Broken Into Dictionary Words
Problem
Given a string s and a dictionary wordDict, return true if s can be segmented into a sequence of one or more dictionary words. Each word may be reused.
Input
s = "leetcode", wordDict = ["leet", "code"]Output
truedp[i] = "the prefix of length i is segmentable". dp[0] = true; dp[i] = true if some j < i has dp[j] = true and s[j..i) is in the dictionary.
def 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];
}