Word Break - CollegeStash

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

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)

/**
 * @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

Demo

Related