leetcode140. Word Break II

huayeluoliuhen 发布于2019-08-15 14:29 / 611人阅读

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

题目要求

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.

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

现在有一个非空字符串s和一个非空的字典wordDict。现在向s中添加空格从而构成一个句子，其中这个句子的所有单词都存在与wordDic中。字典中不包含重复的单词。

思路和代码

我们只需要每次从当前字符串中进行一次分割，该分割保证前一部分为字典中的一个单词，然后我们将后一部分作为子字符串递归的传入方法获取子字符串的分割。

catsanddog
cat | sanddog
cat | sand | dog 
cats | anddog
cats | and | dog

但是单纯的递归会带来超时的情况，尤其是当字典中的单词出现大量包含的情况，如:[a,aa,aaa,aaaa]，而输入为aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
我们可以利用HashMap缓存来解决这个问题，其中key为子字符串，value为其分割的结果的列表。

    private Map> cache = new HashMap>();
    public List wordBreak(String s, List wordDict) {
        if(cache.containsKey(s)) return cache.get(s);
        List result = new ArrayList();
        if(s.length()==0){
            result.add("");
            return result;
        }
        
        for(String word : wordDict){
            if(s.startsWith(word)){
                List subWords = wordBreak(s.substring(word.length()), wordDict);
                for(String subWord : subWords){
                    result.add(word + (subWord.isEmpty() ? "" :" ") + subWord);
                }
                
                
            }
        }
        cache.put(s, result);
        return result;
    }

想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~

私有云混合云 break-word word-break cdn140 Leetcod

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

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

leetcode-140- Word Break II

摘要：衔接点在于的前后连贯，拼成所有的满足条件的前后两个要连续。递归问题，要记得设置终止退出条件设置成形式，就不需要过程中了，直接在此进行叠加累计应用将一个连续序列分成所有元素可能的组合情况。重点明确不必要的地方，可以不用去进行计算。题目阐述：广度搜索问题。计算出所有可能的情况。衔接点在于segs的前后连贯，拼成所有的满足条件的segs 前后两个seg要连续。递归问题，要记得设置终...

joyvw 2019-07-30 17:28 评论0 收藏0
Word Break I, II & Concatenated Words

摘要：所以现在里面应该存可以使长度为所有可能的里的最后一个。有两种写法，一个就是直接写成数组的形式，不能形成的。结束之后，第二步就是通过里面保存的，一步一步回溯找到所有结果。直接的会超时，考虑记忆化搜索。所以事先对排序。 Word Break 链接：https://leetcode.com/problems... 这种找一个词由多个词组成的题，是拿dp或者dfs来解，dp本质上其实也是dfs...

sunsmell 2019-08-14 17:20 评论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
[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