@ 代码随想录算法训练营第8周（C语言）|Day51（动态规划）
Day51、动态规划（包含题目 139.单词拆分 ）
139.单词拆分
题目描述
给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
题目解答
char* substring(int j,int i,char*s){
int len=i-j;
char*ret=(char*)malloc(sizeof(char)*(len+1));
for(int z=0;z<len;z++ ){
ret[z]=s[++j];
}
ret[len]='\0';
return ret;
}
bool comparestring(char **wordDict,char*s,int wordDictSize){
for(int i=0;i<wordDictSize;i++){
if(strcmp(wordDict[i],s)==0){
return true;
}
}
return false;
}
bool wordBreak(char* s, char** wordDict, int wordDictSize) {
int len=strlen(s);
int dp[len+1];
char s1[len+1];
for(int i=1,j=0;i<=len;i++){
s1[i]=s[j++];
dp[j]=0;
}
dp[0]=1;
for(int i=1;i<=len;i++){
for(int j=0;j<i;j++){
char*ret=substring(j,i,s1);
if(comparestring(wordDict,ret,wordDictSize)&&dp[j]==1){
dp[i]=1;
}
}
}
if(dp[len]==1){
return true;
}
return false;
}
题目总结
多重背包问题。
