【LeetCode-面试算法经典-Java实现】【139-Word Break(单词拆分)】
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了【LeetCode-面试算法经典-Java实现】【139-Word Break(单词拆分)】,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2782字,纯文字阅读大概需要4分钟。
内容图文
【139-Word Break(单词拆分)】
【LeetCode-面试算法经典-Java实现】【全部题目文件夹索引】
原题
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"
.
题目大意
给定一个字符串s和单词字典dict,确定s能否够切割成一个或多个单词空格分隔的序列。
解题思路
一个字符串S,它的长度为N。假设S能够被“字典集合”(dict)中的单词拼接而成,那么所要满足的条件为:
* F(0, N) = F(0, i) && F(i, j) && F(j, N);
* 这样子,假设我们想知道某个子串是否可由Dict中的几个单词拼接而成就能够用这种方式得到结果(满足条件为True, 不满足条件为False)存入到一个boolean数组的相应位置上,这样子,最后boolean 数组的最后一位就是F(0, N)的值,为True表示这个字符串S可由Dict中的单词拼接,否则不行!
代码实现
算法实现类
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
publicclassSolution {publicbooleanwordBreak(String s, Set<String> wordDict) {
// 參数校验if (s == null || s.length() < 1 || wordDict == null || wordDict.size() < 1) {
returnfalse;
}
// 标记是否匹配,match[i]表表[0, i-1]都匹配int length = s.length();
boolean[] match = newboolean[length + 1];
match[0] = true;
for (int i = 1; i < length + 1; i++) {
for (int j = 0; j < i; j++) {
if (match[j] && wordDict.contains(s.substring(j, i))) {
// f(0,n) = f(0,i) + f(i,j) + f(j,n)
match[i] = true;
break;
}
}
}
return match[length];
}
// 以下是还有一种解法。可是会超时publicbooleanwordBreak2(String s, Set<String> wordDict) {
// 參数校验if (s == null || s.length() < 1 || wordDict == null || wordDict.size() < 1) {
returnfalse;
}
Map<Character, Set<String>> wordMap = new HashMap<>(wordDict.size());
// 将全部開始字符同样的单词放入一个Set中for (String word : wordDict) {
Set<String> set = wordMap.get(word.charAt(0));
if (set == null) {
// 新创建一个set放入Map中
set = new HashSet<>();
wordMap.put(word.charAt(0), set);
}
// 单词存入set中
set.add(word);
}
return wordBreak(s, 0, wordMap);
}
/**
* 搜索字符串能否够被切割成单词串
*
* @param s 字符串
* @param idx 处理的開始位置
* @param wordMap 单词字典,開始字符同样的在同一个set集合中
* @return 搜索结果
*/publicbooleanwordBreak(String s, int idx, Map<Character, Set<String>> wordMap) {
if (idx >= s.length()) {
returntrue;
}
Set<String> words = wordMap.get(s.charAt(idx));
if (words != null) {
for (String word : words) {
// idx之前的字符已经匹配,假设从ide之后起匹配word单词if (s.startsWith(word, idx)) {
// 递归处理boolean result = wordBreak(s, idx + word.length(), wordMap);
// 假设满足条件,返回trueif (result) {
returntrue;
}
}
}
}
returnfalse;
}
}
评測结果
点击图片,鼠标不释放,拖动一段位置,释放后在新的窗体中查看完整图片。
特别说明
欢迎转载。转载请注明出处【http://blog.csdn.net/derrantcm/article/details/47774547】
原文:http://www.cnblogs.com/gccbuaa/p/7241406.html
内容总结
以上是互联网集市为您收集整理的【LeetCode-面试算法经典-Java实现】【139-Word Break(单词拆分)】全部内容,希望文章能够帮你解决【LeetCode-面试算法经典-Java实现】【139-Word Break(单词拆分)】所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。