每天一道算法題（七）Leetcode – Word BreakII (Java)

題目：

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”],

* the solution is [“cats and dog”, “cat sand dog”].

本題沒有想出使用dfs的做法，是以找了一下解法。

思路：核心是字元串中的單詞和字典項比較

1.本題使用了dp和dfs兩種算法

2.根據題意，背包中不在放flag，而是存放和題意相符的單詞

3.利用dfs遞歸算法取得所有結果

代碼：

public static List<String> wordBreak(String s, Set<String> dict) {

        List<String>[] dp = new List[s.length() + ];
        dp[] = new ArrayList();

        for (int i =  ; i < s.length() ; i++) {
            if (dp[i] == null) {
                continue;
            }

            for (String word : dict) {
                int len = word.length();
                int end = i + len;
                if(end > s.length()) 
                    continue;

                if (s.substring(i , end).equals(word)) {
                    if (dp[end] == null) {
                        dp[end] = new ArrayList();
                    }
                    dp[end].add(word);
                }
            }
        }

        List<String> result = new ArrayList<String>();
        if (dp[s.length()] == null) {
            return result;
        }
        List<String> temp = new ArrayList<String>();
        dfs(dp, s.length(), result, temp);

        return result;
    }

    /**
     * 遞歸解法，需要有一個終止條件
     * 此問題的終止條件是end <= 
     * @param dp
     * @param end
     * @param result
     * @param tmp
     */
    public static void dfs(List<String> dp[],int end,List<String> result, List<String> tmp){
        if (end <= ) {
            String path = tmp.get(tmp.size() - );
            for (int i=tmp.size()-; i>=; i--) {
                path += " " + tmp.get(i);
            }
            result.add(path);
            return;
        }
        for (String word : dp[end]) {
            tmp.add(word);
            dfs(dp, end - word.length(), result, tmp);
            tmp.remove(tmp.size() - );
        }
    }
    @Test
    public static void main(String[] args){
        String str = "catsanddog";
        String[] strs = {"cat", "cats", "and", "sand", "dog"};  
        Set<String> dict = new HashSet<String>(Arrays.asList(strs));  
        System.out.println(wordBreak(str, dict));
    }