leetcode: 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".
解题思路：
1. 这题很好理解，意思就是给定一个字符串和一组字符串，如果该字符串能分成数组字符串里面的子字符串，那么就返回 true ,反之就返回 false;
2. 对于此类问题，我们应该条件反射的想到用动态规划来求解
3. 设置一个数组用 dp[] 来存储每个阶段的状态，其中 dp[i] 表示 0~i 个字符串可以拆分
4. 在第二层循环中，将当前字符串分成 0~j 和 j~i ,并判断当前字符串是否包含在其中
代码如下：
public boolean wordBreak(String s, Set<String> dict) {
int len = s.length();
boolean [] dp = new boolean[len + 1];
dp[0] = true;
// 当前字符串：0~i
for(int i = 1; i <= len; i++){
// 将当前的字符串再进行拆分，查看它是否包含在 dict 中
for(int j = 0; j < i; j++){
// dp[j] 是前面已经计算出来的结果
if(dp[j] && dict.contains(s.substring(j,i))){
dp[i] = true;
break;
}
}
}
return dp[len];
}原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读