[LeetCode] Word Break II

[LeetCode] Word Break II

題目鏈接：https://oj.leetcode.com/problems/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"].

思路：還是DFS遞歸遍歷。采用動態規劃比較麻煩，需要存儲當前位置能夠實現 word break的所有結果的和，空間復雜度很高，不劃算，代碼寫起來還很麻煩。

public class Solution {
    public List wordBreak(String s, Set dict) {
        List rsList = new ArrayList();
        if (s == null || s.length() < 1 || dict == null) {
            return rsList;
        }
        
        wordBreakHelper(s, 0, "", dict, rsList);
        
        return rsList;
    }
    
    public void wordBreakHelper(String s, int start, String tempStr, Set dict, List rsList)  {
        if (start >= s.length()) {
            rsList.add(tempStr);
            return;
        }
        
        for (int i = start + 1; i <= s.length(); i++) {
            String temp = s.substring(start, i);
            if (dict.contains(temp)) {
                String newTempStr;
                if (tempStr.length() < 1) {
                    newTempStr = temp;
                } else {
                    newTempStr = tempStr + " " + temp;
                }
                
                wordBreakHelper(s, i, newTempStr, dict, rsList);
            }
        }
    }
}