Word Break I, II & Concatenated Words

sunsmell 发布于2019-08-14 17:20 / 3179人阅读

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

Word Break

链接：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()];
    }
}

Word Break II

链接：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的有点像。

Concatenated Words

链接：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;
        }
    }
}

GPU云服务器云服务器 break-word word-break II ii6

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/66575.html

[Leetcode] Word Search I&amp;II 二维字符矩阵查找单词

摘要：复杂度时间空间为长度，为大小空间复杂度是是因为我用存信息，只动态地存当前的路径如果用来存信息的话空间复杂度就是时间复杂度对每个点都要作为起始点，对于每个起始点，拓展一次有四个可能性四个邻居，要拓展次长度为。思路暴力搜索带走。 Word Search I Given a 2D board and a word, find if the word exists in the grid. ...

LuDongWei 2019-08-14 14:06 评论0 收藏0
leetcode126. Word Ladder II

摘要：题目要求相比于，要求返回所有的最短路径。至于如何生成该有向图，则需要通过广度优先算法，利用队列来实现。将每一层的分别入栈。如果遇到则至该层结尾广度优先算法结束。通过这种方式来防止形成圈。题目要求 Given two words (beginWord and endWord), and a dictionarys word list, find all shortest transfo...

cooxer 2019-08-15 11:13 评论0 收藏0
[LeetCode] 126. Word Ladder II

摘要：存放过程中的所有集合为所有的结尾，则顺序存放这个结尾对应的中的所有存放同一个循环的新加入的，在下一个循环再依次对其中元素进行进一步的把首个字符串放入新，再将放入，并将键值对放入，进行初始化 Problem Given two words (start and end), and a dictionary, find all shortest transformation sequenc...

wayneli 2019-08-14 14:27 评论0 收藏0
leetcode140. Word Break II

摘要：题目要求现在有一个非空字符串和一个非空的字典。现在向中添加空格从而构成一个句子，其中这个句子的所有单词都存在与中。题目要求 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 ...

huayeluoliuhen 2019-08-15 14:29 评论0 收藏0
[Leetcode] Word Break 单词分解

摘要：所以只要验证满足这个条件，我们则可以确定这个较长的字符串也是可分解的。同时，我们用数组记录下字符串长度递增时可分解的情况，以供之后使用，避免重复计算。当遍历完这个词典并找出所有以第一个字母开头的词以后，我们进入下一轮搜索。 Word Break I Given a string s and a dictionary of words dict, determine if s can ...

Ververica 2019-08-14 12:24 评论0 收藏0