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];
  }