前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >leetcode-139-单词拆分(递归超时,动归解决)

leetcode-139-单词拆分(递归超时,动归解决)

作者头像
chenjx85
发布2018-09-29 15:22:41
1.1K0
发布2018-09-29 15:22:41
举报
文章被收录于专栏:chenjx85的技术专栏

题目描述:

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明:

  • 拆分时可以重复使用字典中的单词。
  • 你可以假设字典中没有重复的单词。

示例 1:

代码语言:javascript
复制
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。

示例 2:

代码语言:javascript
复制
输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
     注意你可以重复使用字典中的单词。

示例 3:

代码语言:javascript
复制
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

要完成的函数:

bool wordBreak(string s, vector<string>& wordDict) 

说明:

1、这道题给定一个string,和一个vector,vector中装着多个string类型的变量。

要求判断给定的string能不能通过在string中添加空格,从而变成一个个单词,而这些单词存在于给定的vector中。

比如给定的string是“catsandog”,给定的vector是['cats','dog','sand','and','cat']。

我们会发现并不能添加空格,进而刚好可以切分成vector中的单词。

所以返回false,如果可以切分的话,就返回true。

2、我们还是看1中的例子,我们可以发现首先有cats和cat两个选择,接下来又有sand和and两个选择。

所以这其实可以用递归来做,但是递归对于一些测试样例太耗时了。所以递归超时了。

感兴趣的同学可以看一下递归的代码,如下:(附详解)

代码语言:javascript
复制
    bool dfs(string s,vector<string>& wordDict)
    {
        if(s.size()==0)return true;//退出条件,字符串已经为空了
        int i;
        for(string word:wordDict)//逐个判断可不可以是当前单词
        {
            i=0;
            while(i<word.size())//判断可不可以到达当前单词的尾部
            {
                if(word[i]!=s[i])
                    break;
                i++;
            }
            if(i==word.size())//如果可以到达当前单词的尾部
            {
                if(dfs(s.substr(i,s.size()-i),wordDict))//那么更新一下字符串,进入下一层递归
                    return true;
            } 
        }
        return false;//如果没有一个单词可以匹配,那么返回false
    }
    bool wordBreak(string s, vector<string>& wordDict) 
    {
        return dfs(s,wordDict);//直接进入深度优先搜索的递归
    }

上述代码没有错误,只不过需要的时间太多了,导致超时。

递归不能做,那应该就是动态规划的做法了。

动态规划注重状态,在这道题中也就是每个字符能不能到达的状态。

比如catsandog,第一个字符c在字典中没有找到对应的word来匹配,ca也找不到对应的word来匹配,cat可以找到,cats也可以找到。

而catsa找不到直接对应的,发现前一个的cats可以到达,于是判断一下a能不能找到对应的,发现没有。

再发现再前一个的cat可以到达,于是判断一下sa能不能找到匹配的,发现不能,接着再往前找,但是都没找到。

我们由此可以发现每一位的状态定义,首先从字符串的最开始,到当前位,看一下有没有直接匹配的。

如果有,那么进行下一位的状态判断。

如果没有,那么往前看,前面哪一位状态是可以到达的,从这一位的下一位开始,到当前位结束,这一部分看可不可以在字典中直接匹配到。

如果还是不行,那么再往前找哪一位状态是可以到达的,同样从这一位的下一位开始,到当前位结束,这一部分可不可以在字典中直接匹配到。

……

最终没有找到的话,那么把这一位的状态定义为不可到达的,再进行下一位的状态判断。

代码如下:(附详解)

代码语言:javascript
复制
    bool judge(string &s,int start,int end,vector<string>& wordDict)
    {//判断s从start开始,到end结束,能不能在字典中找到直接匹配的
        string t=s.substr(start,end-start+1);//记得要+1
        for(string word:wordDict)//看一下哪个单词能够直接匹配
        {
            if(word==t)
                return true;
        }
        return false;
    }
    bool wordBreak(string s, vector<string>& wordDict)//要完成的子函数
    {
        vector<bool>flag(s.size(),0);//定义一个vector,存储每一位的状态
        int j;
        for(int i=0;i<s.size();i++)//计算每一位的状态
        {
            flag[i]=judge(s,0,i,wordDict);//首先看一下能不能找到直接匹配的
            if(flag[i]==0)//如果不能
            {
                j=i-1;//那么j=i-1,j往前面走
                while(j>=0)
                {
                    if(flag[j]==1)//如果某一位的状态是可以到达的
                    {
                        flag[i]=judge(s,j+1,i,wordDict);//那么判断一下从这一位的下一位开始,到i结束,这一部分可不可以找到匹配的
                        if(flag[i]==1)break;//如果可以,那么break循环,接着去计算下一位的状态
                    }
                    j--;//如果没有break循环,那么必然没有找到匹配的,那么j再往前走。如果一直没找到,那么状态不会更改,还是0
                }
            }
        }
        return (flag.back()==1);//最终看一下最后一位的状态是不是可以到达的,如果是,那么返回true     
    }

上述代码实测4ms,beats % of cpp submissions。

笔者自己的个人总结,动态规划有两个特点:

1、强调每一位的状态。

2、每一位的状态计算往往跟前几位有关系,也就是存在对前面状态的依赖性。

有时候是对前面一位状态的依赖,有时候是对前面几位,主要看解决题目的需要而定,而这道题是对前面的所有状态的依赖。

还是挺有趣的一道题目。

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2018-09-06 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目描述:
  • 要完成的函数:
  • 说明:
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档