$\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}$