Leetcode139-单词划分

$\textrm{Problem Description : }$$\href{https://leetcode.cn/problems/word-break/}{\textrm{LeetCode139-单词划分}}$

类似区间合并，检验是否可以用所给单词拼接出目标单词

$\textrm{Solution:}$

一个简单的思路是，如果单词$s[0:n]$已经确定可以拼接出，而又存在单词$s[n:m]$，那么显然$s[0:m]$是可以得到的。因此，我们只关心前半部分是否能够拼接出，而不关心是如何拼接出的，然后与已有的单词组合，将状态进行转移：

1.正向转移：用$dp[i]$表示$s[0:i]$是否能够得到，若能，则枚举所有单词匹配$s[i+1]$开始的部分，并将匹配成功的终点设置为true

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int n = s.size();
        bool *dp = new bool [n+1]();
        dp[0] = true;
        for(int i = 0;i < n;i++)
        {
            if(!dp[i]) continue;
            for(const string & word: wordDict)
            {
                int m = word.size();
                if(i+m <= n && s.substr(i,m) == word)
                    dp[i+m] = true;
            }
        }
        return dp[n];
    }
};                                                                                                                                                              

$\textrm{Author}$@$\href{http://kuroko.info}{\textrm{Kuroko}}$

$\textrm{GitHub}$@$\href{https://github.com/SuperKuroko}{\textrm{SuperKuroko}}$

$\textrm{LeetCode}$@$\href{https://leetcode-cn.com/u/kuroko177/}{\textrm{kuroko177}}$

$\textrm{Last Modified: 2023-02-21 19:18}$