leetcode-139. 单词拆分(记忆化搜索|动态规划)

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元售后保障童叟无欺

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

说明：

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

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。
示例 2：

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

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

记忆化搜索


class Solution { 
   
public:
    set<string>m;
    bool wordBreak(string s, vector<string>& wordDict) { 
   
        if(s == "")return true;
        if(m.find(s) != m.end())return false;
        for(auto &a : wordDict){ 
   
            int len = a.size();
            if(s.size() >= len){ 
   
                string t = s.substr(0,len);
                if(t == a && wordBreak(s.substr(len),wordDict))return true;
            }
        }
        m.insert(s);
        return false;
    }
};

动态规划

const int N = 1e5 + 10;

class Solution { 
   
public:
    bool wordBreak(string s, vector<string>& wordDict) { 
   
        int n = s.size();
        bool f[N] = { 
   false};
        f[0] = true;
        for(int i = 1;i <= n;i ++){ 
   
            for(auto &w : wordDict){ 
   
                int l = i - w.size();
                int len = w.size();
                if(l >= 0 && w == s.substr(l,len)){ 
   
                    f[i] = f[i] | f[l];
                }
            }
        }
        return f[n];
    }
};