Word Break II leetcode

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"].

用DFS来解, 但是要像word break里那样判定s是否能被切分然后再进行dfs切分, 否则会超时

public class Solution {
    public List<String> wordBreak(String s, Set<String> wordDict) {
        List<String> res = new ArrayList<String>();
        if (s == null || s.length() == 0) {
            return res;
        }
        boolean[] table = new boolean[s.length() + 1];
        table[0] = true;
        for (int i = 0; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if(table[j] && wordDict.contains(s.substring(j,i))) {//j+1到i字符
                    table[i] = true;
                    break;
                }
            }
        }
        if (table[s.length()] == false) {
            return res;
        }
        StringBuilder sb = new StringBuilder();
        helper(res, s, wordDict, 0, sb);
        return res;
    }
    public void helper(List<String> res, String s, Set<String> wordDict, int pos, StringBuilder sb) {
        if (pos == s.length()) {
            res.add(sb.toString());
            return;
        }
        for (int i = pos; i <= s.length(); i++) {
            String tem = s.substring(pos, i);
            if (wordDict.contains(tem)) {
                int len = sb.length();
                if (len > 0) {
                    sb.append(" ");
                }
                sb.append(tem);
                helper(res, s, wordDict, i, sb);
                sb.delete(len, sb.length());
            }
        }
    }
}