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"] . 이 문제는 모든 결과를 요구하는데, 분명히 귀속될 것이다.brute force의 해법을 먼저 쓰세요.

public class Solution {
    public List<String> wordBreak(String s, Set<String> dict) {
        List<String> res = new ArrayList<String>();
        if(s.length() == 0 || s == null)
            return res;
        recursive(s, 0, dict, "", res);
        return res;
    }
    
    public void recursive(String s, int index, Set<String> dict, String string, List<String> res){
        if(index >= s.length()){
            res.add(string);
            return;
        }
        StringBuilder builder = new StringBuilder();
        for(int i = index; i < s.length(); i++){
            builder.append(s.charAt(i));
            if(dict.contains(builder.toString())){
                String str = string.isEmpty() ? builder.toString() : (string + " " + builder.toString());
                recursive(s, i + 1, dict, str, res);
            }
        }
    }
}

빅데이터 집합은 통하지 않는다.인터넷에서 가지를 자르는 방법을 보았는데 DP의 사상을 이용하는 것이다. 만약에 어떤 점 i가 이전의 검색에서 결과를 얻지 못하면 이후에는 검색을 하지 않는다.

public class Solution {
    public List<String> wordBreak(String s, Set<String> dict) {
        List<String> res = new ArrayList<String>();
        if(s.length() == 0 || s == null)
            return res;
        boolean[] possible = new boolean[s.length() + 1];
        Arrays.fill(possible, true);
        recursive(s, 0, dict, "", res, possible);
        return res;
    }
    
    public void recursive(String s, int index, Set<String> dict, String string, List<String> res, boolean[] possible){
        if(index >= s.length()){
            res.add(string);
            return;
        }
        StringBuilder builder = new StringBuilder();
        for(int i = index; i < s.length(); i++){
            builder.append(s.charAt(i));
            //only perform search if there are possible solutions in level i + 1
            if(dict.contains(builder.toString()) && possible[i + 1]){
                String str = string.isEmpty() ? builder.toString() : (string + " " + builder.toString());
                int beforeSearch = res.size();
                recursive(s, i + 1, dict, str, res, possible);
                //if the result size is not changed after the search, then there is no solution at i
                if(beforeSearch == res.size())
                    possible[i + 1] = false;
            }
        }
    }
}