`
huntfor
  • 浏览: 201093 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

[leetcode]Word Break II

 
阅读更多

本博文的方法有点投机取巧了,新博文中采取了更通用的解法,新博文地址:[leecode]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.

For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].

 Word Break的加强,很自然的想到了DFS,但是对于一些比较变态的例子会超时,我这里采用了一种很极端的方法:首先判断s能由dict中单词组成的必要条件。即,s中的所有字母都必须出现在dict中的单词中。如果s中存在一个字母,在dict中不存在,那么直接返回找不到即可。

虽然AC了,但是总是觉得很别扭,不过暂时没想到更好的方法。

 List<String> result = new ArrayList<String>();
	public List<String> wordBreak(String s, Set<String> dict) {
		StringBuilder sb = new StringBuilder();
		boolean hasUnexistLetter = false;
		ok:for(int i = 0; i < s.length(); i++){//判断是否存在某个字母不出现在字典中
			for(String str: dict){
				if(str.contains(s.charAt(i)+"")){
					continue ok;
				}
			}
				hasUnexistLetter = true;
		}
		if(!hasUnexistLetter){
			dfs(sb, s, dict);
		}
		return result;
	}
	private void dfs(StringBuilder pre,String s,Set<String> dict){
		if(s == null || s.length() == 0){
			result.add(new String(pre).substring(1));
			return;
		}
		for(int i = 1 ; i <= s.length(); i++){
			String str = s.substring(0, i);
			if(dict.contains(str)){
				pre.append(' ').append(str);
				String suffix = s.substring(i);
				dfs(pre, suffix, dict);
				pre.delete(pre.length() - 1 - str.length(),pre.length());
			}
		}
	}

 

分享到:
评论

相关推荐

    python-leetcode题解之140-Word-Break-II

    python python_leetcode题解之140_Word_Break_II

    js-leetcode题解之140-word-break-ii.js

    javascript js_leetcode题解之140-word-break-ii.js

    python-leetcode题解之139-Word-Break

    python python_leetcode题解之139_Word_Break

    js-leetcode题解之139-word-break.js

    javascript js_leetcode题解之139-word-break.js

    LeetCode题解(java语言实现).pdf

    * Word Break、Word Break II:该题目要求将字符串分割成单词,实现方法使用了动态规划和回溯算法。 * Word Ladder:该题目要求将一个单词转换成另一个单词,实现方法使用了广度优先搜索算法。 二、树和图 * ...

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

    LeetCode最全代码

    318| [Maximum Product of Word Lengths](https://leetcode.com/problems/maximum-product-of-word-lengths/) | [C++](./C++/maximum-product-of-word-lengths.cpp) [Python](./Python/maximum-product-of-word-...

    leetcode苹果-word-break:断字

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

    LeetCode题解 - Java语言实现-181页.pdf

    5. Word Break II 单词断词II是一个变体的问题,要求将字符串断词为单词,并且可以使用动态规划或Trie树来解决该问题。 6. Word Ladder 单词梯是一个字符串问题,要求将一个单词转换为另一个单词,并且每次转换...

    Leetcode题目+解析+思路+答案.pdf

    - **Word Break**:判断一个字符串是否可以拆分为一个词汇表中的单词序列。 7. **链表(Linked List)**: - **Linked List Cycle**:检测链表中的环。 - **Remove Duplicates from Sorted List**:从已排序的...

    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

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

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

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

    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动态规划

    leetcode刷题之动态规划

    var wordBreak = function(s, wordDict) { let n = s.length; let dp = new Array(n + 1).fill(false); dp[0] = true; for (let i = 0; i ; i++) { for (let j = 0; j ; j++) { if (dp[j] && wordDict....

    python-leetcode面试题解之第139题单词拆分-题解.zip

    def wordBreak(s, wordDict): wordDict = set(wordDict) # 将单词列表转换为集合,加快查找速度 dp = [False] * (len(s) + 1) # 初始化动态规划数组,dp[i]表示s[:i]是否可以被拆分 dp[0] = True # 空字符串可以...

    uber leetcode

    #### 一、Word Break II - **知识点:**动态规划、回溯算法。 - **题目描述:**给定一个非空字符串s和一个包含非空单词列表的词典wordDict,在字符串中增加空格来构建一个句子,使得句子中所有的单词都在词典中。...

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

    leetcode530-leetcode:力扣在线评委

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

    扩展矩阵leetcode-Leetcode:LeetcodeAnswer-Java

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

Global site tag (gtag.js) - Google Analytics