思路:
1 DFS 但是TLE
2 DP 还需多练。。。
http://www.programcreek.com/2012/12/leetcode-solution-word-break/
http://xixiaogualu.blogspot.com/2013/10/leetcode-word-break.html
package Level5;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.Set;
/**
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".
*
*/
public class S147 {
public static void main(String[] args) {
Set<String> dict = new HashSet<String>();
dict.add("aaa");
dict.add("aaaa");
String s = "aaaaaaa";
System.out.println(wordBreak(s, dict));
System.out.println(wordBreak2(s, dict));
}
// DP
public static boolean wordBreak(String s, Set<String> dict) {
// 如果canBreak[i]为true,则s[0...(i-1)]能被拆分
boolean[] canBreak = new boolean[s.length()+10];
canBreak[0] = true; // 初始化
for(int i=0; i<s.length(); i++){
if(canBreak[i] == false){
continue;
}
for(String dictS : dict){
int len = dictS.length();
int end = i + len;
if(end > s.length()){
continue;
}
if(s.substring(i, end).equals(dictS)){
canBreak[end] = true;
}
}
}
return canBreak[s.length()];
}
// DFS TLE
public static boolean wordBreak2(String s, Set<String> dict) {
return dfs(s, dict, 0);
}
public static boolean dfs(String s, Set<String> dict, int start){
if(start >= s.length()){
return true;
}
for(String dictS : dict){
int len = dictS.length();
if(start+len<=s.length() && s.substring(start, start+len).equals(dictS)){
if(dfs(s, dict, start+len)){
return true;
}
}
}
return false;
}
}
分享到:
相关推荐
示例 1:输出:3解释:- "a" 是 "abc" 的子字符串。示例 3:输出:3解释:patterns 中的每个字符串都作为子字符串出现在 word "ab
LeetCode 205的题目是“同构字符串”(Isomorphic Strings),要求判断两个字符串是否是同构的。如果字符串s可以通过字符替换得到字符串t,那么这两个字符串是同构的。所有出现的字符都必须用另一个字符替换,同时...
LeetCode判断字符串是否循环 LeetCode解题思路总结 1.两数之和 方法一:Map 1.创建一个map 2.for循环遍历nums数组 3.用target减nums[i]得到key 4.检查map里面是否有key var twoSum = function (nums, target) { var ...
给定一个字符串,逐个翻转字符串中的每个单词。 示例 1: 输入: “the sky is blue” 输出: “blue is sky the” 示例 2: 输入: ” hello world! “ 输出: “world! hello” 解释: 输入字符串可以在前面或者后面...
翻转字符串里的单词一、题目描述二、题解实现1. 方法一:双指针2. 方法二:库函数3. 方法三:一行实现法 一、题目描述 题目:151.翻转字符串里的单词 难度:中等 给定一个字符串,逐个翻转字符串中的每个单词。 示例...
leetcode思维导图-字符串
0758. 字符串中的加粗单词标签:字典树、数组、哈希表、字符串、字符串匹配难度:中等题目大意给定一个关键词集合 words 和一个字符串 s。要求:在所有 s
LeetCode判断字符串是否循环 LeetCode leetcode刷题 语言:python 平台:jupyter notebook 字符串 day01 验证回文字符串 思路:先对字符串判断,是否为空...翻转字符串里的单词 思路 先将字符串去掉开头和结尾的空格 以
请注意,你可以假定字符串里不包括任何不可打印的字符。 示例: 输入: Hello, my name is John 输出: 5 题解: 首先使用trim()去掉开头和结尾的空格,再使用split按照空格切分。 scala代码: /** * \\s表示 空格,...
LeetCode问题28要求实现strStr()函数,即在一个主字符串(haystack)中找出第一个出现的指定子字符串(needle)的索引,如果不存在,则返回-1。如果needle为空字符串,返回0。 这段Fortran程序定义了一个strStr函数,它...
java java_leetcode面试题解双指针之第151题反转字符串中的单词
给定一个字符串和一个字符串字典,找到字典里面最长的字符串,该字符串可以通过删除给定字符串的某些字符来得到。如果答案不止一个,返回长度最长且字典顺序最小的字符串。如果答案不存在,则返回空字符串。 示例1:...
字符串压缩题目解题思路图解代码实现实现结果补充 面试题 01.06. 字符串压缩 题目来源:https://leetcode-cn.com/problems/compress-string-lcci 题目 字符串压缩。利用字符重复出现的次数,编写一种方法,实现...
LeetCode 76. 最小覆盖子串 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 "" 。 本测试数据是第265个测试用例,字符串长度...
LeetCode判断字符串是否循环 Leetcode 2017年4月12日 455 分蛋糕: 有g个孩子,s块蛋糕,每个孩子有一个贪心因子m,每块蛋糕可大可小n,若蛋糕大小n大于等于m,则可以分配这块蛋糕给这个孩子。每个孩子只能分得一块...
1055.Shortest_Way_to_Form_String_形成字符串的最短路径【LeetCode单题讲解系列】
给定一个字符串,找出没有重复字符的最长子字符串的长度。 示例 1: Input: "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3. 示例 2: Input: "bbbbb" Output: 1 Explanation: The ...
LeetCode判断字符串是否循环 leetcode leetcode exercises,algorithms part! TwoSum: 1.key point: unorderd_map(16ms), map(24ms) 2.大概是前50%的样子,并不知道如何进一步提升性能 addTwoNums: 1.新建ListNode...
翻转字符串里的单词 simplifyPath 简化路径 restoreIPAddresses 复原IP地址 threeSum 三数之和 search 搜索旋转排序数组 1. 3. 9. 75. 209. 219. 167. 268. 344. 349. 454. 447. 695. 674. string 字符串 20. 150. ...
LeetCode判断字符串是否循环 LeetCodeForCZY Solution For LeetCode 题目说明: 1、两数之和:(TwoSum) 给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。 可以假设每个输入只对应一种答案,且同样的...