### The 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.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

Check LeetCode link for more details and example input & output.

### Dynamic Programming Solutions

#### A Top Down Approach

``````  public boolean wordBreak(String s, List<String> wordDict) {
return wordBreak(s, 0, wordDict, new Boolean[s.length()]);
}
boolean wordBreak(String s, int index, List<String> wordDict, Boolean[] dp) {
if (index == s.length()) {
return true;
} else if (index > s.length()) {
return false;
}
if (dp[index] != null) {
return dp[index];
}
for (String word: wordDict) {
if (index + word.length() > s.length()
|| !s.substring(index, index + word.length()).equals(word)) {
continue;
}
if (wordBreak(s, index + word.length(), wordDict, dp)) {
dp[index] = true;
return true;
}
}
dp[index] = false;
return false;
}
``````

#### A Bottom Up Approach

`dp[i]` is a sub problem, whose input is a sub string of `s`, starting at the index `i`.

`dp[i]` is true, if there is at least one word `w` in `wordDict`, that makes `dp[i + len(w)]` true.

The base case is that `dp[len(s)]` is true. And, `dp[0]` is the original problem.

Below is a Java solution.

``````  public boolean wordBreak(String s, List<String> wordDict) {
boolean[] dp = new boolean[s.length() + 1];
dp[s.length()] = true; // the base case

for (int i = s.length() - 1; i >= 0; i--) {
for (String word: wordDict) {
if (i + word.length() < s.length() + 1
&& s.substring(i, i + word.length()).equals(word)) {
dp[i] = dp[i + word.length()];
}

if (dp[i]) {
break;
}
}
}
return dp[0];
}
``````