前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >LeetCode 139 Word Break

LeetCode 139 Word Break

作者头像
ShenduCC
发布2018-12-13 15:56:40
3870
发布2018-12-13 15:56:40
举报
文章被收录于专栏:算法修养

LeetCode 139. Word Break

我使用的方法是区间DP

代码语言:javascript
复制
class Solution {
public:
    map<string,int> m;
    int dp[1005][1005];
    bool wordBreak(string s, vector<string>& wordDict) {
        
        for(int i=0;i<wordDict.size();i++)
            m[wordDict[i]]=1;
        memset(dp,0,sizeof(dp));
        fun(s);
        if(dp[0][s.length()-1]==1)
            return true;
        else
            return false;
        
    }
    
    void fun(string s)
    {
        int len=s.length();
        for(int l=1;l<=len;l++)
        {
            for(int i=0;i+l-1<len;i++)
            {
                int j=i+l-1;
                string s1 = s.substr(i,l);
                if(m[s1]==1)
                    dp[i][j]=1;
                else{
                    for(int k=i;k<j;k++)
                    {   
                        if(dp[i][k]==1&&dp[k+1][j]==1)
                         dp[i][j]=1;
                    }
                } 
            }
        }
    }
};
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2018-11-15 ,如有侵权请联系 cloudcommunity@tencent.com 删除

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

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

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

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档