`

LeetCode - Word Break II

 
阅读更多

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

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

Solution1:

递归调用。但是发现会超时。故要采用第二种办法。

public List<String> wordBreak(String s, Set<String> dict) {
    List<String> result = new ArrayList<String>();
    breakWord(result, s, 0, dict, "");
    return result;
}

public void breakWord(List<String> result, String s, int start, Set<String> dict, String word) {
    if(start>=s.length()) {
        result.add(word.substring(1));
        return;
    }
    for(int i=start; i<s.length(); i++) {
        String prefix = s.substring(start, i+1);
        if(dict.contains(prefix)) {
            String newWord = word + " " + prefix;
            breakWord(result, s, i+1, dict, newWord);
        }
    }
}

 

Solution2:

动态规划。如果f[i]=true,代表s.substring(i)可以分解;反之则不能被分解。

public List<String> wordBreak(String s, Set<String> dict) {
    List<String> result = new ArrayList<String>();
    Boolean[] f = new Boolean[s.length()+1];
    Arrays.fill(f, true); //默认从哪里都可以break,后面检查后再更新
    dpWordBreak(result, f, s, 0, dict, "");
    return result;
}

public void dpWordBreak(List<String> result, Boolean[] f, String s, int start, Set<String> dict, String word) {
    if(start>=s.length()) {
        result.add(word.substring(1)); // 去掉开头的空格
        return;
    }
    for(int i=start; i<s.length(); i++) {
        String prefix = s.substring(start, i+1);
        if(dict.contains(prefix) && f[i+1]) {
            String newWord = word + " " + prefix;
            int beforeSize = result.size();
            dpWordBreak(result, f, s, i+1, dict, newWord);
            if(beforeSize == result.size()) {
                //如果结果列表长度不变,说明word的i+1~n子串部分没有break成功
                f[i+1] = false;
            }
        }
    }

 

分享到:
评论

相关推荐

    wordbreakleetcode-WordBreak-Leetcode-139:一种使用动态规划来确定一个词是否可以作为给定词典中所有词的串

    断字leetcode WordBreak-Leetcode-139 Leetcode 问题 139(中) 问题中使用的技术:动态规划

    lrucacheleetcode-leetcode-in-go:leetcode-in-go

    lru缓存leetcode Go 中解决的一些 Leetcode 问题 大批 3sum-0015 买卖股票的最佳时机-0121 最多水的容器-0011 contains-duplicate-0217 find-minimum-in-rotated-sorted-array-0153 ...word-break-0139 图形

    leetcode苹果-word-break:断字

    leetcode 苹果断字 给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,确定 s 是否可以被分割成一个或多个字典单词的空格分隔序列。 笔记: 字典中的同一个词可能会在切分中重复使用多次。...word. E

    扩展矩阵leetcode-Leetcode:LeetcodeAnswer-Java

    扩展矩阵leetcode Leetcode Leetcode Answer-Java 数组 11.乘最多水容器 ...wordBreak 279.完全平方数 numSquares 排序 56.合并区间 merge 75.颜色分类 sortColors 179.最大数 largestNumber 324.摆

    LeetCode最全代码

    137 | [Single Number II](https://leetcode.com/problems/single-number-ii/) | [C++](./C++/single-number-ii.cpp) [Python](./Python/single-number-ii.py) | _O(n)_ | _O(1)_ | Medium ||| 190 | [Reverse Bits]...

    LeetCode:LeetCode解决方案

    preorder-traversal链表reorder-list链表linked-list-cycle-ii链表linked-list-cycle动态规划word-break-ii动态规划word-break链表copy-list-with-random-pointer复杂度single-number-ii复杂度single-number动态规划

    leetcode338-coding_notebook:编码_笔记本

    第 338 章概括 [(雅虎)4。...问题/数组和字符串/140.word_break_ii.md) [151. 反转字符串中的单词](Leetcode Problems/Array and String/151.reverse_words_in_a_string.md) [167. Two Sum 2 - In

    wordbreakleetcode-WordBreak:“断字”问题的解决方案。用C#编写

    断字leetcode 断字 “断字”问题的解决方案。 用 C# 编写 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. ...

    leetcode530-leetcode:力扣在线评委

    leetcode 530 力扣在线评委 # 问题 困难 解决方案 1 简单的 2 中等的 3 中等的 12 中等的 22 中等的 39 中等的 94 中等的 108 中等的 122 中等的 136 中等的 144 中等的 167 中等的 238 中等的 260 中等的 268 中等...

    LintCode 582: Word Break II

    Word Break II Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences. Example Example 1...

    gasstationleetcode-leetcode:LeetcodeOJ解决方案

    leetcode 【演示记录】 报告 展示 2017/03/06 1.二和,167.二和二 2107/03/06 15.3 总和,16.3 总和最近,18.4 总和,11.最多水的容器 2017/03/09 62.Unique Paths, 63.Unique Paths II, 64.Minimum Path Sum 2017/...

    dynamic-programming:动态编程

    动态编程递归无重复每个子问题只能评估一次天真的递归方法由于重复而花费指数时间自上而下的回忆这是递归的深度优先搜索实现缓存重复工作自下而上基于依赖图将递归转换为依赖图它是有向无环图您可以使用拓扑排序对......

    cpp-算法精粹

    Word Break II Dungeon Game House Robber House Robber II House Robber III Range Sum Query - Immutable Range Sum Query 2D - Immutable 图 Clone Graph 位操作 Reverse Bits Repeated DNA Sequences Number of ...

Global site tag (gtag.js) - Google Analytics