Published
Edited
Sep 26, 2019
wordBreak = ({s, dict}) => {
const word_Break = (s, hashSet, start) => {
if (start === s.length) {
return true
}
for (let end = start + 1; end <= s.length; end++) {
if (hashSet.includes(s.substring(start, end)) && word_Break(s, hashSet, end)) {
return true
}
}
return false
}
return word_Break(s, dict, 0)
}
wordBreakDP = ({s, dict}) => {
let dp = Array(s.length + 1).fill(false)
dp[0] = true
for (let i = 1; i <= s.length; i++) {
for (let j = 0; j < i; j++) {
if (dp[j] && dict.includes(s.substring(j, i))) {
dp[i] = true
break
}
}
}
return dp[s.length]
}
testWordBreakApproach(tests[0])
testWordBreakApproach(tests[1])
testWordBreakApproach(tests[2])
tests = [
{s: "leetcode", dict: ["leet", "code"]},
{s: "applepenapple", dict: ["apple", "pen"]},
{s: "catsandog", dict: ["cats", "dog", "sand", "and", "cat"]}
]
approach = wordBreakDP
testWordBreakApproach = (input, raw) => raw ? approach(input) : `${approach(input) ? `True, segments ${input.dict}`:`False, segments ${input.dict} do not`} compose word ${input.s}`
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
