139.单词拆分

最新推荐文章于 2024-09-22 20:09:34 发布

迅~

最新推荐文章于 2024-09-22 20:09:34 发布

阅读量66

点赞数

分类专栏： LeetCode刷题笔记文章标签：动态规划算法 c语言

本文链接： https://blog.csdn.net/m0_64560763/article/details/125285295

版权

LeetCode刷题笔记专栏收录该内容

440 篇文章 5 订阅

订阅专栏

题目

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/word-break
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

示例

思路

1.动态规划，创建一个dp[n]记录s中第i个字符之前的在字典中是否匹配，匹配成功记录为1，不匹配或者没有匹配记录为0

循环遍历s，更新s数组中每个字符的匹配情况，并记录在dp[i]中，因为不匹配成功就记录为0，所以创建dp是就初始化为0，只有当匹配成功时才更新dp[i]

最后判断dp[n]是否为1，是说明n之前的字符都可以匹配。否说明n之前有没有不匹配的

2.递归，剪枝，也可以利用递归，每次将匹配成功之后，将前面的字符串剪去，剩余的字符递归再进行比较，最后返回是否匹配

代码

/*
*wordBreak：利用字典查找字符串子串
char * s：字符串
char ** wordDict：字典
int wordDictSize:字典长度
返回值：存在返回true，不存在返回false
*/
bool wordBreak(char * s, char ** wordDict, int wordDictSize){
   int sLen = strlen(s);
   int dp[sLen + 1];
   memset(dp , 0 , sizeof(dp));
   dp[0] = 1;
   int k;
   int wordLen;
   int i,j;
   for(i = 1; i <= sLen; i++)
   {
       for(j = 0; j < wordDictSize; j++)
       {
           wordLen = strlen(wordDict[j]);
           k = i - wordLen;
           if(k < 0)
           {
               continue;
           }
           int m = strncmp(s + k , wordDict[j],wordLen);
           if(!m)
           {
                dp[i] = (dp[k] && 1) || dp[i];              
           }
       }
   } 
   return dp[sLen] == 1 ? true : false;
}