`

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

  题目意思 : 将字符串分开,但是划分后的子串必须是dict集合中的元素!

  当时看错了题目,以为dict中的所有元素组合成s

public class Solution {
    // 注意这里是一个set集合,也就是说,不会有重复的元素
    public boolean wordBreak(String s, Set<String> dict) {
        int len = s.length();
        if (len == 0) return true;
        int size = dict.size();
        if (size == 0) return false;
     // 他来记录j位前的元素都匹配   
        boolean[] flag = new boolean[len + 1];
        flag[0] = true;
// 注意这里利用了substring(j , i) 截取的字符串为 j -> i-1 , 所以 i+1
        for (int i = 1 ; i <= len ; i++) {
            for (int j = 0 ; j < i ; j++) {
                if (flag[j] && dict.contains(s.substring(j ,i))) {
                    flag[i] = true;
                    break;
                }
            }
        }
        return flag[len];
    }
}

 Discuss 中另一种方法:

   备忘的方法 :

public Set<String> unmatch=new HashSet<String>(); // 这个集合用来记录不匹配的
public boolean wordBreak(String s, Set<String> dict) {

    if(s.length()==0){
        return true;
    }
   int count=s.length();
// 如果s不匹配,那么后面的递归调用就不会进行!
     if (unmatch.contains(s)){
         return false;
     }
     for(int i=1;i<=count;i++){
         if(dict.contains(s.substring(0,i))&&wordBreak(s.substring(i,count),dict)){
             return true;
         }
     }

    unmatch.add(s);    
     return false;

}
}

 

分享到:
评论

相关推荐

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

    在提供的代码库"WordBreak-Leetcode-139-master"中,你可能会找到一个具体的实现,它可能包括以下部分: - 主函数,接收字符串sentence和词汇表wordDict作为输入参数。 - 动态规划的逻辑,包括初始化dp数组和遍历...

    浅析word-break work-wrap的区别

    object.style.wordBreak="keep-all"   值 描述 normal 使用浏览器默认的换行规则。 break-all 允许在单词内换行。 keep-all 只能在半角空格或连字符处换行。 兼容性: 举个栗子: CSS Co

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

    css 英文换行 css(word-wrap/break)使纯英文数字自动换行

    为了解决这个问题,我们可以利用`word-wrap`和`word-break`两个CSS属性。 `word-wrap`属性主要用于控制是否允许内容在单词内部换行。它有两个主要的取值: 1. `normal`:这是默认值,遵循浏览器的默认换行规则。在...

    webfrom-列表文本内容自动换行 word-break-keep-all;word-wrap-n.pdf

    &lt;HeaderStyle HorizontalAlign="Center"&gt;&lt;/HeaderStyle&gt; &lt;ItemStyle CssClass="dxgv"&gt;&lt;/ItemStyle&gt; ... myDataGrid_d.Attributes.Add("style", "word-break:keep-all;word-wrap:normal");

    css中强制换行word-break、word-wrap、white-space区别实例说明

    复制代码代码如下:”c1″&gt;safjaskflasjfklsajfklasjflksajflksjflkasfdsafdsfksafj&lt;/div&gt;&lt;div class=c1&gt;This is all English. This is all English. This is all English.&lt;/div&gt;&lt;div class=c1&gt;全是中文的情况。...

    word-break:break-all和word-wrap:break-word区别总结

    `word-break:break-all` 和 `word-wrap:break-word` 是CSS中用于控制文本换行的两个属性,它们都有各自的特点和适用场景。 首先,`word-break:break-all` 的作用是在任何可能的位置强制进行单词内部的换行。这意味...

    使用Word2Vec大语言模型和RNN结构生成文本序列的简单示例代码.txt

    break input_text.append(output_word) input_text = input_text[1:] print(output_word) ``` #### 四、扩展与优化 - **更大规模的数据集**:为了提高模型的性能和生成文本的质量,可以使用更大规模的语料库来...

    前端开源库-breakword

    **前端开源库-breakword** `breakword` 是一个专门针对前端开发的开源库,它的主要功能是处理文本断行问题,特别是在多语言环境下确保文本在指定长度内正确断开,保持良好的显示效果。这个库的核心在于它能计算字符...

    FastReport中文折行问题修正

    wordbreak属性通常用于控制文本中的单词断行规则,如果设置为true,FastReport会尝试在单词内部进行折行,而在处理中文时,这样做可能会破坏词组的完整性。因此,保持wordbreak属性默认或设置为false,可以让...

    实现label文字以指定长度自动换行

    例如,`word-wrap: break-word;`可以让长单词在容器边界处断开。 5. **事件监听**:在某些情况下,可能需要根据窗口大小的变化动态调整`Label`的换行行为。为此,可以监听窗口的`resize`事件,然后重新计算并设置...

    单词拆分(Java代码).docx

    WordBreak solution = new WordBreak(); String s1 = "leetcode"; List&lt;String&gt; wordDict1 = Arrays.asList("leet", "code"); System.out.println(solution.wordBreak(s1, wordDict1)); // 输出 true String ...

    HTML 标签中的连续的英文折断

    默认情况下,浏览器会尝试避免在单词内部进行断行,但我们可以设置`word-break: break-all`来允许单词在任何地方断行,或者使用`word-wrap: break-word`来确保单词不会超出容器的边界,而是会在单词内部合适的位置...

    javascript-leetcode面试题解动态规划问题之第139题单词拆分-题解.zip

    function wordBreak(s, wordDict) { const dp = Array(s.length + 1).fill(false); dp[0] = true; for (let i = 1; i ; i++) { for (const word of wordDict) { if (s.startsWith(word, i - word.length) && ...

    word-wrap与word-break 属性的概述及浏览器默认处理

    本文主要探讨了两个与文本换行密切相关的CSS属性:`word-wrap` 和 `word-break`,以及浏览器对它们的默认处理方式。 一、浏览器默认处理文本换行 默认情况下,浏览器采用`word-wrap: normal`策略,这意味着当一行...

    常见动态规划问题总结

    1.三角形找一条从顶到底的最小路径 2.最大子数组和 3.回文最小划分次数 4.最佳时间买卖股票 5. 判断字符串s3是否由s1,s2交叉存取组成 6.给定一个矩形表格,求从顶到底的最小和 ...10.单词分解Word Break

    分词.docx

    break word_list.insert(0, longest_word) i -= len(longest_word) return word_list ``` 在上面的 Python 实现中,我们首先加载了一个词典,然后从文本的结尾开始扫描,每次扫描都从当前位置开始,向前遍历,...

    CSS word-wrap同word-break的区别

    兼容 IE 和 FF 的换行 CSS 推荐样式 最好的方式是 word-wrap:break-word; overflow:hidden; 而不是 word-wrap:break-word; word-break:break-all; 也不是 word-wrap:break-word; overflow:auto; 在 IE 下没有任何...

Global site tag (gtag.js) - Google Analytics