[leetcode]140. Word Break II DP+DFS解法

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. You may assume the dictionary does not contain duplicate words.

給定一個非空串S和一個包含非空單詞的清單Dict，給串S添加空格建構一個句子使得每一個單詞是Dict中的一個單詞。其中Dict中無重複單詞。

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

解析：看完題第一個反應就是深搜，快速生成代碼：

void dfs(String s, List<String> ret, List<String> Dict, List<String> buff) {
        if (s.length() == 0) {
            ret.add(String.join(" ",buff));
            return;
        }

        for (int i = 0; i < Dict.size(); i++) {
            if (s.startsWith(Dict.get(i))) {
                String t = Dict.get(i);
                buff.add(t);
                dfs(s.substring(t.length()), ret, Dict, buff);
                buff.remove(buff.size() - 1);
            }
        }
    }

    public List<String> wordBreak(String s, List<String> wordDict) {

        List<String> ret = new ArrayList<>();
        List<String> buff = new ArrayList<>();
        dfs(s, ret, wordDict, buff);
        return ret;
    }
           

結果是TLE，挂在下面Case上：

"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"]
           

想想很明顯，是dfs中的for進行了許多無用的搜尋造成的，解決方法無非就是DP或剪枝。看題目标簽是DP，修改成DP解法。

void dfs(int [][] dp, List<String> ret, List<String> buff,int step,List<String> Dict) {
        
        if(step == dp.length){
            ret.add(String.join(" ", buff));
            return;
        }
        
        for(int i = 0; i < dp.length; i++){
            int strind = dp[i][step];
            if(strind > 0){
                buff.add(Dict.get(strind - 1));
                dfs(dp,ret, buff,step+Dict.get(strind - 1).length(), Dict);
                buff.remove(buff.size()-1);
            }
        }
        
    }
    
    private void show(int [][]dp){
        for(int i = 0; i < dp.length; i++){
            
            System.out.println();
            for(int j = 0; j < dp.length; j++){
                System.out.printf("%3d", dp[i][j]);
            }
        }
    }
    
    public List<String> wordBreak(String s, List<String> wordDict) {

        List<String> ret = new ArrayList<>();
        //将字典加入到map中
        Map<String,Integer> dic = new HashMap<>();
        for(int i = 0; i < wordDict.size(); i++){dic.put(wordDict.get(i),i+1);}
        
        int sLen = s.length();
        int [][] dp = new int[sLen][sLen];
        
        boolean connected[] = new boolean[sLen];
        //填表
        for(int i = s.length()-1; i > -1; i--){
            
            int increLen = s.substring(i).length();
            for(int j = 0; j < increLen; j++){//System.out.println(s.substring(i, i+j+1));
                int ti = i+j+1;
                if(dic.containsKey(s.substring(i, ti)) && (i+j+1==sLen || connected[ti])){
                    connected[i] = true;
                    dp[j][i]=dic.get( s.substring(i, ti) );
                }
            }
        }
        
        //show(dp);
        
        //dfs周遊結果。
        dfs(dp,ret, new ArrayList<String>(),0,wordDict);
        
        return ret;
        
    }
           

經驗總結：

對于這種求組合，拆分不确定位置的題，幾乎都可以使用深搜解決。可以再搜尋的條件上增加限制減少搜尋空間。如果時間複雜度還是相差太多，就要考慮是否應該使用DP來避免反複求值了。實際上，相比于例如Combination，SubSet，全排列或者迷宮周遊這種，其實如果經驗豐富還是很容易看出來是否應該使用DP。比如組合問題，如果使用子問題劃分，狀态轉移并且Memorazition這套東西，并沒有任何意義，而是純粹的搜尋才能生成解空間。而對于這題，問題的關鍵在于對于一個相同長度的串有多少種字典單詞可以組合而成。深搜重點在目标串的拆分上，而DP的重點是字典單詞的組合上面。對于一道沒見過的題目，隻有抓住問題的關鍵，才能選擇正确的算法。

轉載于:https://www.cnblogs.com/yumingle/p/6652911.html