LeetCode[139] Word Break

wyk1184 发布于2019-08-14 15:04 / 2995人阅读

摘要：复杂度思路用来记录已经判断过的，每次判断是否开头是在中的出现的字符串。代码保留已经搜索过的信息

LeetCode[139] Word Break

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

For example, given
s = "leetcode",
dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

DFS + Memorization

复杂度
O(N^2),O(N)

思路
用map来记录已经判断过的string，每次判断是否开头是在map中的出现的字符串。

代码

Map map = new HashMap<>();
public boolean wordBreak(String s, Set wordDict) {
    if(s.length() == "") return true;
    // use map to 保留已经搜索过的信息；
    if(map.containsKey(s)) return map.get(s);
    for(String d : wordDict) {
        if(s.startsWith(d)) {
            if(wordBreak(s.substring(d.length()), wordDict) {
                return true;
            }
        }
    }
    map.put(s, false);
    return false; 
}

GPU云服务器云服务器 break-word word-break 139企业邮箱 LeetCode

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

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

leetcode-139-Word Break

摘要：边界点注意区分清楚，连贯起来。应用思想应用，涉及到前后需要保持状态的匹配计算，要保留并利用中间状态。相似问题动态规划，利用前面的状态。题目简介： 1.完全按照dict中的word进行切分匹配，一个char都不差 2.由于是连续匹配，所以是首尾相接，所以涉及到动态规划思想,需要保留上一个动态 3.广度递归非常耗时，不知道什么原因。 4.边界点注意区分清楚，连贯起来。应用：思想应用，涉...

wwolf 2019-07-30 17:28 评论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
[LintCode/LeetCode] Word Break

Problem Given a string s and a dictionary of words dict, determine if s can be break into a space-separated sequence of one or more dictionary words. Example Given s = lintcode, dict = [lint, code]. R...

dunizb 2019-08-14 15:30 评论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-140- Word Break II

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

joyvw 2019-07-30 17:28 评论0 收藏0