[Leetcode] Word Break II

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].

DP problem. Use the same idea as in here. However, since we need to find all possible ways to split the string, the break statement should be removed. What's more, we need to reconstruct how to split the string, we need to store this information, so we use match[i][j] to indicate whether s[i...j] is a word in dict. Then use a recurse method to reconstruct all possible split.

public class Solution {
    
 public List<String> wordBreak(String s, Set<String> dict) {
  int n = s.length();
  boolean[] dp = new boolean[n];
  boolean[][] match = new boolean[n][n];
  
  for(int i = 0; i < n; i++) {
      dp[i] = false;
      for(int j = 0; j <= i; j++) {
          if(j == 0) {
              if(dict.contains(s.substring(0, i+1)) == true) {
                  dp[i] = true;
                  match[0][i] = true;
              }
          }
          else {
                  if(dp[j-1] == true && dict.contains(s.substring(j, i+1)) == true) {
                      dp[i] = true;
                      match[j][i] = true;
                  }
          }
      }
  }
  List<String> result = new ArrayList<String>();
  if(dp[n-1] == false)
      return result;
  dfs(match, s, "", 0, n, result);
  return result;
 }
 
 private void dfs(boolean[][] match, String s, String current, int beg, int n, List<String> result) {
     if(beg == n)
         result.add(current);
     else {
         for(int i = beg; i < n; i++) {
             if(match[beg][i] == true) {
                 StringBuffer sb = new StringBuffer(current);
                 sb.append(s.substring(beg, i+1));
                 if(i != n-1)
                     sb.append(" ");
                 dfs(match, s, sb.toString(), i+1, n, result);
             }
         }
     }
 }
}