Given a non-empty string “word” can it be broken into a list of non-empty words contained in a dictionary ? The words can be repeated.
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | public class Solution { public boolean wordBreak(String s, List<String> wordDict) { return word_Break(s, new HashSet(wordDict), 0, new Boolean[s.length()]); } public boolean word_Break(String s, Set<String> wordDict, int start, Boolean[] memo) { if (start == s.length()) { return true; } if (memo[start] != null) { return memo[start]; } for (int end = start + 1; end <= s.length(); end++) { if (wordDict.contains(s.substring(start, end)) && word_Break(s, wordDict, end, memo)) { return memo[start] = true; } } return memo[start] = false; } } |
JavaScript (ES6)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 | /** * @param {string} s * @param {string[]} wordDict * @return {boolean} */ const wordBreak = (s, wordDict) => canWordBreak(s, 0, wordDict); const dp = {}; const canWordBreak = (word, index, wordDict) => { if (index === word.length) { return dp[index] = true; } if (dp[index] !== undefined) { return dp[index]; } for (let breakIndex = index + 1; breakIndex <= word.length; breakIndex++) { if (wordDict.indexOf(word.substring(index, breakIndex)) > -1 && canWordBreak(word, breakIndex, wordDict)) { return dp[index] = true; } } return dp[index] = false; } // console.log(wordBreak("catsandog", // ["cats","dog","sand","and","cat"])); // false |