绑定完请刷新页面
取消
刷新

分享好友

×
取消 复制
[LeetCode] Word Break
2015-06-17 00:00:00

Word Break

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

解题思路:

解法1,回溯法。但会超时。其时间复杂度为len!

class Solution {
public:
    bool wordBreak(string s, unordered_set<string>& wordDict) {
        return helper(s, wordDict);
    }
    
    bool helper(string s, unordered_set<string>& wordDict){
        if(s==""){
            return true;
        }
        int len = s.length();
        for(int i=1; i<=len; i++){
            if(wordDict.find(s.substr(0, i))!=wordDict.end() && helper(s.substr(i), wordDict)){
                return true;
            }
        }
        return false;
    }
};

解法2,动态规划。对于d[i]表示字符串S[0,..., i]费否能够被字典拼接而成。于是有


d[i] = true, 如果s[0,...i]在字典里面

d[i] = true, 如果存在k,0<k<i,且d[k]=true,s[k+1, .., i]在字典里面

d[i] = false, 不存在这样的k

代码如下:

class Solution {
public:
    bool wordBreak(string s, unordered_set<string>& wordDict) {
        int len = s.length();
        if(len == 0){
            return true;
        }
        bool d[len];
        memset(d, 0, len * sizeof(bool));
        if(wordDict.find(s.substr(0, 1)) == wordDict.end()){
            d[0] = false;
        }else{
            d[0] = true;
        }
        for(int i=1; i<len; i++){
            for(int k=0; k<i; k++){
                d[i] = wordDict.find(s.substr(0, i+1))!=wordDict.end() || d[k] && (wordDict.find(s.substr(k+1, i-k))!=wordDict.end());
                if(d[i]){
                    break;
                }
            }
        }
        return d[len-1];
    }
};

时间复杂度为O(len^2)


另外,一个非常好的解法就是添加一个字符在s前面,使得代码更加简洁。

class Solution {
public:
    bool wordBreak(string s, unordered_set<string>& wordDict) {
        s = "#" + s;
        int len = s.length();
        bool d[len];
        memset(d, 0, len * sizeof(bool));
        d[0] = true;
        for(int i=1; i<len; i++){
            for(int k=0; k<i; k++){
                d[i] = d[k] && (wordDict.find(s.substr(k+1, i-k))!=wordDict.end());
                if(d[i]){
                    break;
                }
            }
        }
        return d[len-1];
    }
};


转载请注明:康瑞部落 » [LeetCode] Word Break
分享好友

分享这个小栈给你的朋友们,一起进步吧。

康瑞部落
创建时间:2020-05-21 17:48:23
本小栈的内容主要包括以下几个方面: 1、有关计算机项目开发的个人心得 2、有关算法与数据结构方面的研究 3、其他计算机相关知识 4、读书笔记与书摘 5、个人兴趣的交流 6、生活琐事的记录 7、转载的美文
展开
订阅须知

• 所有用户可根据关注领域订阅专区或所有专区

• 付费订阅:虚拟交易,一经交易不退款;若特殊情况,可3日内客服咨询

• 专区发布评论属默认订阅所评论专区(除付费小栈外)

栈主、嘉宾

查看更多
  • Ruiyuan Li
    栈主

小栈成员

查看更多
  • 栈栈
  • 一号管理员
  • gaokeke123
  • chengxuwei
戳我,来吐槽~