Word Break I, II & Concatenated Words

摘要：所以现在里面应该存可以使长度为所有可能的里的最后一个。有两种写法，一个就是直接写成数组的形式，不能形成的。结束之后，第二步就是通过里面保存的，一步一步回溯找到所有结果。直接的会超时，考虑记忆化搜索。所以事先对排序。

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

这种找一个词由多个词组成的题，是拿dp或者dfs来解，dp本质上其实也是dfs。这道题要判断输入的词能否由字典里的单词组成，那么可以用个boolean的dp数组。

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，两种找的方法，一个是j从0到i - 1循环，还有一种是traverse整个dict，j = i - word.length()。当字典很大，s不长的时候，用第一种，当字典不大，但是s很长的时候用第二种。这题现在给的dict是个list不是set没法O(1)判断s[j, i] in dict，所以用第二种来写。

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

和上一题不同的是，这道题要返回所有可能的组合。所以现在dp[i]里面应该存可以使长度为i所有可能的String里的最后一个word。dp有两种写法，一个就是直接写成数组：List[]的形式，不能形成的dp[i] = null。还有一个是用个hashmap：Map，用hashmap的好处是如果s很长而且用dict能组合成的长度不是很多的话，map用的空间相对少。
dp结束之后，第二步就是通过dp里面保存的word，一步一步回溯找到所有结果。

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本质上就是dfs，这题可以dfs来做。直接的dfs会超时，考虑记忆化搜索。两种方式：一个是用dp[i]来记录(i,n)有valid的string，参考这个人的博客：
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记录走过的路，这样就不会重复搜索了，和dp其实是一样的，但是这里把整个路径都保存了，之后就不需要再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的写法原理和path sum的有点像。

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

这道题可以用dp的方法，和word break一样，多加个循环，复杂度是O(N^3)，这道题注意下，字典比较大，用第二种来写dp function会超时，只能用第一种。

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里面的优化，感觉很好，思路是一个word要想被其他词组成，其他词的长度必然是<这个词的。所以事先对words排序。这个lc里面一开始没加“word.length() > 1”的条件，测试里面会出现一个字母的结果，很神奇啊，到现在也不知道错在哪。。

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一个一个往里加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, 没有优化，结果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;
        }
    }
}