[编程题]word-break

dict=["leet", "code"].

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

```/**
* 方法二：
* 状态转移方程：
* f(i) 表示s[0,i]是否可以分词
* f(i) = f(j) && f(j+1,i); 0 <= j < i;
*
*/
public boolean wordBreak2(String s, Set<String> dict){
int len = s.length();
boolean[] arrays = new boolean[len+1];
arrays[0] = true;
for (int i = 1; i <= len; ++i){
for (int j = 0; j < i; ++j){
if (arrays[j] && dict.contains(s.substring(j, i))){
arrays[i] = true;
break;
}
}
}
return arrays[len];
}```

```        int len = s.length();
vector<bool> dp(len+1,false);
dp[0]=true;
for(int pos=0;pos<len;++pos)
for(int i=pos;dp[pos] && i<len;++i)
if (dict.find(s.substr(pos,i-pos+1))!=dict.end())
dp[i+1]=true;
return dp[len];```

```//有几个需要注意的边界点
import java.util.*;
public class Solution {
public boolean wordBreak(String s, Set<String> dict) {
int i,j;
boolean array[]=new boolean[s.length()+1];//此处的Array大小
array[0]=true;//此处的初始化
for(i=1;i<array.length;i++) {
for(j=0;j<i;j++) {
if(array[j]&&dict.contains(s.substring(j, i))) {
array[i]=true;//此处的SubString
break;
}
}
}
return array[array.length-1];//此处的返回值

}
}
```

```import java.util.*;
//题意：把wordDict中的元素进行组合，可以重复使用，是否可以拼成s
public class Solution {
public boolean wordBreak(String s, Set<String> dict) {
boolean[] res = new boolean[s.length() + 1];
res[0] = true;
//i循环的目的是，确定能不能拼成以i为下标结尾的字符串
for (int i = 1; i <= s.length(); i++) {
for (int j = 0; j < i; j++) {
if(res[j]&&dict.contains(s.substring(j, i))){
res[i]=true;
//只要找到一个 能拼成以i为下标结尾的字符串，就可以跳出循环
break;
}
}
}

return res[s.length()];
}
}```

```class Solution {
public:
bool wordBreak(string s, unordered_set<string> &dict) {
int len = s.length();
vector<bool> v(len+1,false);
v[0] = true;
for(int i = 1;i <= len; i++)
{
for(int j = i-1; j >= 0; j--)
{
if(v[j] && dict.find(s.substr(j,i-j))!= dict.end())
{
v[i] = true;
break;
}
}
}
return v[len];
}
};```

```class Solution {
public:
bool wordBreak(string s, unordered_set<string> &dict) {
int l = s.length();
vector<bool> dp(l+1, false);
dp[0] = true;
for(int i=0;i<l;i++)
for(int j=i;j<l && dp[i];j++)
if(dict.find(s.substr(i, j-i+1)) != dict.end())
dp[j+1] = true;
return dp[l];
}
};
```

```/**
* 出发点：给定字符串s的每个字符i
* 最优解：对于每个i之前的字符序列，分为j(0<=j<=i)前面的序列和j后面的序列，求解i转化为求解j和i-j
* 状态d(i)：i之前的字符序列分段后的字符串能不能在字典中找到
* 递推公式：d(i) = d(i)||(d(j)&sub(i-j)), 其中j=0~i
*/
import java.util.*;
public class Solution {
public boolean wordBreak(String s, Set<String> dict) {
int len = s.length();
boolean[] d = new boolean[len];
for (int k=0; k<len; k++)
d[k] = false;
String sub = null;
boolean subFlag = false;

for (int i=0; i<len; i++) {
for (int j=0; j<=i; j++) {
sub = s.substring(j, i+1);
subFlag = dict.contains(sub);
if (j==0) d[i] = subFlag;
else d[i] = d[i]||(d[j-1]&&subFlag);
}
}

return d[len-1];
}
}```

//动态规划问题
public class WordBreak
{
public boolean wordBreak(String s, Set<String> dict)
{
if (s == null || s.length() == 0)
{
return true;
}
int len = s.length();
// 正确截取单词的标记(开始索引)
boolean dp[] = new boolean[len + 1];
// 初始
dp[0] = true;
for (int i = 0; i < len; i++)
{
// substring方法 切割字符串 不包含i+1的哪一个位
StringBuilder str = new StringBuilder(s.substring(0, i + 1));
for (int j = 0; j <= i; j++)
{
if (dp[j] && dict.contains(str.toString()))
{
dp[i + 1] = true;
break;
}
// 删除str的第一个字符(因为str是从s的头字符开始截取的)
str.deleteCharAt(0);
}
}
// 如果都能正确匹配 则dp[len]=true
return dp[len];
}
}

```class Solution{
public:
bool wordBreak(string s, unordered_set<string> &dict){
vector<bool>dp(s.size(), false);
for (int j = 0; j < s.size(); j++)if (dict.find(s.substr(j, s.size() - j)) != dict.end())dp[j] = true;
for (int i = s.size() - 2; i >= 0; i--)
for (int j = 0; j <= i; j++)
if (dict.find(s.substr(j, i - j + 1)) != dict.end())dp[j] = dp[j] || dp[i + 1];
return dp[0];
}
};```

## 动态规划问题

### dp[j] :                   子串 s[i..j)是否能被拆分为词典单词     初始化：         dp[0] = true         由于是右开空间s[0]预设为true方便遍历     递推公式：          dp[j] = dp[i] && dp[i,j)即substr(i, j - i)           注意dp[j]是左闭右开空间

```class Solution {
public:
bool wordBreak(string s, unordered_set<string> &dict) {
vector<bool> dp(s.size() + 1);
dp[0] = true;
//字符串结束位置,左闭右开s[i,j)
for(auto j = 1; j <= s.size(); ++j)
for(auto i = j - 1; i >= 0; --i){//字符串起始位置
if(dp[i] && dict.find(s.substr(i, j - i)) != dict.end()){
dp[j] = true;
break;
}
}
return dp[s.size()];

}
};
```

```class Solution {
public:
bool wordBreak(string s, unordered_set<string> &dict) {
if(dict.find(s)!=dict.end()) return true;
int size=s.size();
for(int i=size-1;i>0;--i)
{
string word=s.substr(i);
if(dict.find(word)==dict.end())
continue;
if(wordBreak(s.substr(0,i),dict)) return true;
}
return false;
}
};
```

``````import java.util.Set;

public class Solution {
public boolean wordBreak(String s, Set<String> dict) {
boolean[] dp = new boolean[s.length() + 1];
dp[0] = true;
for (int i = 1; i <= s.length(); i++) {
for (int j = 0; j < i; j++) {
if (dp[j] && dict.contains(s.substring(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[s.length()];
}
}``````

class Solution {
public:
bool wordBreak(string s, unordered_set<string> &dict) {
/*
dp[i]表示string从0到i能够被分割
dp[i] = dp[j]&&substring(j,i) ,其中0<=j<i
*/
int length = s.length();
int *dp = new int[length+1]();
dp[0]=1;
for(int i=1;i<=length;i++){
for(int j=0;j<i;j++){
if(dp[j]==1 && dict.find(s.substr(j,i-j))!=dict.end()){
dp[i]=1;
break;
}
}
}
return dp[length];
}
};

```import java.util.*;
public class Solution {
public boolean wordBreak(String s, Set<string> dict) {
boolean dp[] = new boolean[s.length() + 1];
dp[0] = true;
for (int i = 1; i <= s.length(); ++i) {
for (int j = 0; j < i; ++j) {
if (dp[j] && dict.contains(s.substring(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[s.length()];
}
}
</string>```

1. 字典采用hash表存储；
2. 并根据单词长度把hash表分开，这样查询速度更快；
3. 记录单词步长，只去匹配存在的步长，比如单词全是4个字母，每次step为4就可以了。
```class Solution(object):
def wordBreak(self, s, wordDict):
if len(wordDict) == 0:
return False
l = max(map(lambda x: len(x), wordDict))
m = [{} for i in range(l + 1)]
steps = []
for w in wordDict:
if len(w) not in steps:
steps.append(len(w))
m[len(w)][w] = 1

dp = [0] * (len(s) + 1)
dp[0] = 1
for i in range(len(s)):
if dp[i] == 0:
continue
for step in steps:
if s[i:i + step] in m[step]:
if i + step <= len(s):
dp[i + step] = 1
return dp[len(s)] == 1
```

```import java.util.Set;
public class Solution {
public boolean wordBreak(String s, Set<String> dict) {
if(s == null || s.length() <= 0)
return true;
if(dict == null || dict.size() <= 0)
return false;

boolean[] dp = new boolean[s.length() + 1];
dp[0] = true;
for(int i = 1; i <= s.length(); i++){
for(int j = 0; j < s.length(); j++){
if(dp[j] && dict.contains(s.substring(j, i))){
dp[i] = true;
break;
}
}
}
return dp[s.length()];
}
}
```

```class Solution {
public:
bool wordBreak(string s, unordered_set<string> &dict) {
int n,i,j,len;
n = s.size();
vector<int> can(n+1,0);
string sub;
unordered_set<string>::iterator it;
len = 0;
for(it=dict.begin();it!=dict.end();it++){
if(len < it->size()){len = it->size();}//找到最大子串长。
}
can[n] = 1;
for(i=n-1;i>=0;i--){
sub = "";
for(j=i;j<n;j++){
sub += s[j];
if(j-i<len && dict.count(sub) && can[j+1]){can[i] = 1;}
}
}
return can[0];
}
};
```

```import java.util.Set;
public class Solution {
public boolean wordBreak(String s, Set<String> dict) {
int len = s.length();
// dp[i]表示0到i位可分
boolean[] dp = new boolean[len + 1];
dp[0] = true;
for (int i = 1; i <= len; i++) {
for (int j = 0; j < i; j++) {
if (dp[j] && dict.contains(s.substring(j, i))) {
dp[i] = true;
}
}
}
return dp[len];
}
}```

if(s.empty()&&dict.find("")==dict.end())
return false;
vector<bool> flag(s.size()+1,false);
flag[0] = 1;
for(int i=1;i<=s.size();i++){
for(int j=i-1;j>=0;j--){
if(flag[j]&&dict.find(s.substr(j,i-j))!=dict.end()){
flag[i] = 1;
continue;
}
}
}
return flag[s.size()];

```动态规划，画一个表格，就能看出来
import java.util.*;
public class Solution {
public boolean wordBreak(String s, Set<String> dict) {
int length=s.length();
if(length<1)
return true;
boolean[] dp=new boolean[length+1];//默认值为false
dp[0]=true;
for(int i=0;i<length;i++){
if(dp[i]){
for(int j=i;j<length;j++){
if(dict.contains(s.substring(i,j+1))){
dp[j+1]=true;
}
}
}
}
return dp[length];
}
}```

112条回答 23608浏览

# 通过挑战的用户

• 2019-09-19 16:08:00
• 2019-09-19 15:10:18
• 2019-09-19 14:10:24
• 2019-09-19 13:53:30
• 2019-09-19 13:15:56

# 相关试题

• 扫描二维码，关注牛客网

• 下载牛客APP，随时随地刷题