$\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}$
退出登录?