摘要：所以現(xiàn)在里面應(yīng)該存可以使長(zhǎng)度為所有可能的里的最后一個(gè)。有兩種寫(xiě)法，一個(gè)就是直接寫(xiě)成數(shù)組的形式，不能形成的。結(jié)束之后，第二步就是通過(guò)里面保存的，一步一步回溯找到所有結(jié)果。直接的會(huì)超時(shí)，考慮記憶化搜索。所以事先對(duì)排序。

鏈接：https://leetcode.com/problems...

這種找一個(gè)詞由多個(gè)詞組成的題，是拿dp或者dfs來(lái)解，dp本質(zhì)上其實(shí)也是dfs。這道題要判斷輸入的詞能否由字典里的單詞組成，那么可以用個(gè)boolean的dp數(shù)組。

initialize dp[s.length() + 1], dp[0] = true

dp function: dp[i] = dp[j] & (s[j, i] in dict)

result: dp[s.length()]

第二步的dp function，兩種找的方法，一個(gè)是j從0到i - 1循環(huán)，還有一種是traverse整個(gè)dict，j = i - word.length()。當(dāng)字典很大，s不長(zhǎng)的時(shí)候，用第一種，當(dāng)字典不大，但是s很長(zhǎng)的時(shí)候用第二種。這題現(xiàn)在給的dict是個(gè)list不是set沒(méi)法O(1)判斷s[j, i] in dict，所以用第二種來(lái)寫(xiě)。

public class Solution {
    public boolean wordBreak(String s, List wordDict) {
        /* boolean dp[s.length() + 1]
         * 1. initial: dp[0] = true
         * 2. function: dp[i] = dp[j] & (s[j, i] in dict)
         * 3. result: dp[s.length()]
         */
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for(int i = 1; i < dp.length; i++) {
            for(String word : wordDict) {
                int j = i - word.length();
                if(j >= 0 && dp[j] && s.substring(j, i).equals(word)) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
}

鏈接：https://leetcode.com/problems...

和上一題不同的是，這道題要返回所有可能的組合。所以現(xiàn)在dp[i]里面應(yīng)該存可以使長(zhǎng)度為i所有可能的String里的最后一個(gè)word。dp有兩種寫(xiě)法，一個(gè)就是直接寫(xiě)成數(shù)組：List[]的形式，不能形成的dp[i] = null。還有一個(gè)是用個(gè)hashmap：Map，用hashmap的好處是如果s很長(zhǎng)而且用dict能組合成的長(zhǎng)度不是很多的話，map用的空間相對(duì)少。
dp結(jié)束之后，第二步就是通過(guò)dp里面保存的word，一步一步回溯找到所有結(jié)果。

public class Solution {
    public List wordBreak(String s, List wordDict) {
        /* dp: 
         * map> dp
         * dp function: put(i, word) if s[j, i] = word & j is a key of dp
         * result: dp[s.length()] backtracking
         */
        dp.put(0, new ArrayList());
        dp.get(0).add("");
        for(int i = 1; i < s.length() + 1; i++) {
            for(String word : wordDict) {
                int j = i - word.length();
                if(j >= 0 && s.substring(j, i).equals(word) && dp.containsKey(j)) {
                    if(!dp.containsKey(i)) dp.put(i, new ArrayList());
                    dp.get(i).add(word);
                }
            }
        }
        
        List result = new ArrayList();
        if(!dp.containsKey(s.length())) return result;
        // backtracking
        dfs(result, s.length(), "");
        return result;
    }
    Map> dp = new HashMap();
    
    private void dfs(List result, int pos, String cur) {
        // base case
        if(pos == 0) {
            result.add(cur);
            return;
        }
        for(String word : dp.get(pos)) {
            int j = pos - word.length();
            if(j >= 0 && dp.containsKey(j)) {
                dfs(result, j, word + (cur.equals("") ? "" : " " + cur));
            }
        }
    }
}

dp本質(zhì)上就是dfs，這題可以dfs來(lái)做。直接的dfs會(huì)超時(shí)，考慮記憶化搜索。兩種方式：一個(gè)是用dp[i]來(lái)記錄(i,n)有valid的string，參考這個(gè)人的博客：
http://www.cnblogs.com/grandy...

public class Solution {
    public List wordBreak(String s, List wordDict) {
        List result = new ArrayList();
        dp = new boolean[s.length() + 1];
        Arrays.fill(dp, true);
        // backtracking
        dfs(result, 0, "", s, wordDict);
        return result;
    }
    boolean[] dp;
    
    private void dfs(List result, int pos, String cur, String s, List wordDict) {
        // base case
        if(pos == s.length()) {
            result.add(cur);
            return;
        }
        if(!dp[pos]) return;
        
        for(String word : wordDict) {
            int i = pos + word.length();
            if(i <= s.length() && s.substring(pos, i).equals(word)) {
                int size = result.size();
                dfs(result, i, (cur.equals("") ? "" : cur + " ") + word, s, wordDict);
                if(size == result.size()) dp[i] = false;
            }
        }
    }
}

還有一種，直接拿hashmap記錄走過(guò)的路，這樣就不會(huì)重復(fù)搜索了，和dp其實(shí)是一樣的，但是這里把整個(gè)路徑都保存了，之后就不需要再backtracking找路徑了，參考discussion里面給的：

public class Solution {
    public List wordBreak(String s, List wordDict) {
        // backtracking
        return dfs(s, wordDict);
    }
    Map> map = new HashMap();
    
    private List dfs(String s, List wordDict) {
        if(map.containsKey(s)) return map.get(s);
        // bottom up
        List result = new ArrayList();
        if(s.length() == 0) {
            result.add("");
            return result;
        }
        
        for(String word : wordDict) {
            int i = word.length();
            if(i <= s.length() && s.substring(0, i).equals(word)) {
                List subs = dfs(s.substring(i), wordDict);
                for(String sub : subs) {
                    result.add(word + (sub.equals("") ? "" : " " + sub));
                }
            }
        }
        map.put(s, result);
        return result;
    }
}

這種記憶化dfs的寫(xiě)法原理和path sum的有點(diǎn)像。

鏈接：https://leetcode.com/problems...

這道題可以用dp的方法，和word break一樣，多加個(gè)循環(huán)，復(fù)雜度是O(N^3)，這道題注意下，字典比較大，用第二種來(lái)寫(xiě)dp function會(huì)超時(shí)，只能用第一種。

public class Solution {
    public List findAllConcatenatedWordsInADict(String[] words) {
        List result = new ArrayList();
        Set set = new HashSet(Arrays.asList(words));
        for(String word : words) {
            set.remove(word);
            if(wordBreak(set, word)) result.add(word);
            set.add(word);
        }
        return result;
    }
    
    private boolean wordBreak(Set words, String s) {
        if(s == null || s.length() == 0) return false;
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for(int i = 1; i < dp.length; i++) {
            for(int j = i-1; j >= 0; j--) {
                if(dp[j] && words.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
}

看了discussion里面的優(yōu)化，感覺(jué)很好，思路是一個(gè)word要想被其他詞組成，其他詞的長(zhǎng)度必然是<這個(gè)詞的。所以事先對(duì)words排序。這個(gè)lc里面一開(kāi)始沒(méi)加“word.length() > 1”的條件，測(cè)試?yán)锩鏁?huì)出現(xiàn)一個(gè)字母的結(jié)果，很神奇啊，到現(xiàn)在也不知道錯(cuò)在哪。。

public class Solution {
    public List findAllConcatenatedWordsInADict(String[] words) {
        List result = new ArrayList();
        Arrays.sort(words, (a, b) -> a.length() - b.length());
        Set set = new HashSet();
        for(String word : words) {
            if(word.length() > 1 && wordBreak(set, word)) result.add(word);
            set.add(word);
        }
        return result;
    }
    
    private boolean wordBreak(Set set, String s) {
        if(s == null || s.length() == 0 || set.isEmpty()) return false;
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for(int i = 1; i < dp.length; i++) {
            for(int j = i-1; j >= 0; j--) {
                if(dp[j] && set.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
}

不用set保存word，用trie tree一個(gè)一個(gè)往里加word和查找，其他都和前一種方法一樣。

public class Solution {
    public List findAllConcatenatedWordsInADict(String[] words) {
        tree = new Trie();
        List result = new ArrayList();
        Arrays.sort(words, (a, b) -> a.length() - b.length());
        for(String word : words) {
            if(word.length() > 1 && dfs(word)) result.add(word);
            tree.addWord(word);
        }
        return result;
    }
    Trie tree;
    private boolean dfs(String s) {
        if(s.length() == 0) return true;
        for(int i = 1; i <= s.length(); i++) {
            if(tree.search(s.substring(0, i))) {
                if(dfs(s.substring(i))) return true;
            }
        }
        return false;
    }
    
    class TrieNode {
        TrieNode[] children = new TrieNode[26];
        boolean isWord;
    }
    
    class Trie {
        TrieNode root;
        private int getIndex(char c) {
            return c - "a";
        }
        public Trie() {
            root = new TrieNode();
        }
        public Trie(String[] words) {
            root = new TrieNode();
            for(String word : words) addWord(word);
        }
        
        public void addWord(String word) {
            TrieNode node = root;
            for(int i = 0; i < word.length(); i++) {
                if(node.children[getIndex(word.charAt(i))] == null) node.children[getIndex(word.charAt(i))] = new TrieNode();
                node = node.children[getIndex(word.charAt(i))];
            }
            node.isWord = true;
        }
        
        public boolean search(String word) {
            TrieNode node = root;
            for(int i = 0; i < word.length(); i++) {
                if(node.children[getIndex(word.charAt(i))] == null) return false;
                node = node.children[getIndex(word.charAt(i))];
            }
            return node.isWord;
        }
    }
}

直接用trie tree, 沒(méi)有優(yōu)化，結(jié)果stackoverflow了。。

public class Solution {
    public List findAllConcatenatedWordsInADict(String[] words) {
        tree = new Trie(words);
        List result = new ArrayList();
        for(String word : words) {
            if(word.length() > 1 && dfs(word, 0)) result.add(word);
        }
        return result;
    }
    Trie tree;
    private boolean dfs(String s, int pos) {
        if(s.length() == pos) return true;
        
        for(int i = pos; i <= s.length(); i++) {
            if(pos == 0 && i == s.length()) return false;
            
            if(tree.search(s.substring(pos, i))) {
                if(dfs(s, i)) return true;
            }
        }
        return false;
    }
    
    class TrieNode {
        TrieNode[] children = new TrieNode[26];
        boolean isWord;
    }
    
    class Trie {
        TrieNode root;
        private int getIndex(char c) {
            return c - "a";
        }
        public Trie() {
            root = new TrieNode();
        }
        public Trie(String[] words) {
            root = new TrieNode();
            for(String word : words) addWord(word);
        }
        
        public void addWord(String word) {
            TrieNode node = root;
            for(int i = 0; i < word.length(); i++) {
                if(node.children[getIndex(word.charAt(i))] == null) node.children[getIndex(word.charAt(i))] = new TrieNode();
                node = node.children[getIndex(word.charAt(i))];
            }
            node.isWord = true;
        }
        
        public boolean search(String word) {
            TrieNode node = root;
            for(int i = 0; i < word.length(); i++) {
                if(node.children[getIndex(word.charAt(i))] == null) return false;
                node = node.children[getIndex(word.charAt(i))];
            }
            return node.isWord;
        }
    }
}