leetcode-140- Word Break II

joyvw 发布于2019-07-30 17:28 / 1512人阅读

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

题目阐述：

广度搜索问题。 计算出所有可能的情况。
衔接点在于segs的前后连贯，拼成所有的满足条件的segs
前后两个seg要连续。
递归问题，要记得设置终止退出条件
elems = {len(s): [""]} 设置成dict形式，就不需要过程中copy了，直接在此进行叠加累计

应用：将一个连续序列分成所有元素可能的组合情况。可以用list进行组装，也可以用dict形式进行组装。
重点：==> if i not in elems: 明确不必要的地方，可以不用去进行计算。

class Solution:

    def wordBreak(self, s, wordDict):
        elems = {len(s): [""]}
        wordDict = set(wordDict)
        len_dict = set(len(w) for w in wordDict)

        def sentences(i):
            if i not in elems:
                iters=list()
                for len_iter in len_dict:
                    cur_part=s[i:i+len_iter]
                    if cur_part and cur_part in wordDict:
                        # print("cur_part==>",cur_part)
                        # elems_iter=list()
                        elem_cur=cur_part
                        for item in sentences(i+len_iter):
                            # print("elem_cur==>",elem_cur)
                            iterow= elem_cur + (item and " "+item)
                            # print("iter==>",iterow)
                            iters.append(iterow)
                    # print("iters==>",iters)
                elems[i]=iters
            return elems[i]
        result=sentences(0)
        # print(elems)
        return result

私有云 idc机房托管 break-word word-break break 语言 break

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

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

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