139.分词题目来源：力扣（LeetCode）https://leetcode-cn.com/problems/word-break题目给定一个非空字符串s和一个包含非空单词列表的字典wordDict，判断s是否可以被空格分割成字典中出现的一个或多个单词。解释：字典中的单词在拆分时可以重复使用。您可以假设字典中没有重复的单词。示例1：输入：s="leetcode",wordDict=["leet","code"]输出：true解释：返回true因为“leetcode”可以拆分为“leetcode”。示例2：输入：s="applepenapple",wordDict=["apple","pen"]输出：true解释：返回true因为“applepenapple”可以拆分为“applepenapple”。请注意，您可以重复使用词典中的单词。示例3：输入：s="catsandog",wordDict=["cats","dog","sand","and","cat"]输出：false是细化问题。下面举个例子2来大致说明一下：输入：s="applepenapple",wordDict=["apple","pen"]输出：true这里如果要判断applepenapple是否可以拆分，可以将问题转化为前面的是否j个字符可以拆分加上剩下的子串是否是词表中的一个词，例如：applepen是否可以拆分，如果可以加上apple就表示可以拆分整体。设dp[i]为前i个可拆分的子串，则具体算法如下：拆分非空字符串[0,i-1]是否前i个子串dp[i]为真，如前所述上面，判断分两部分的前半部分是否为真，后半部分是否在词表中：前缀子串dp[j]是否为真，其余子串是否在词表中。具体实现代码如下。代码实现类解决方案：defwordBreak(self,s:str,wordDict:List[str])->bool:#初始化dpdp=[False]*(len(s)+1)dp[0]=True#遍历Stringforiinrange(1,len(s)+1):#j逐渐划分stringforjinrange(i,-1,-1):#判断前缀部分是否为真，其余部分是否为真in单词列表中dp[i]=dp[j]and(s[j:i]inwordDict)#如果为真，跳出循环，已经确定可以拆分，没有needtocontinueifdp[i]:breakreturndp[len(s)]实现结果总结使用动态规划的方法细化问题。标题要求给定的字符串是否可以拆分。字符串可以分为两部分。设dp[i]为第i个可以拆分的子串。dp[i]是否为真取决于以下部分：将字符串分成两部分，判断前缀部分是否为真以及后面部分是否在词表中。文章为原创，如果您觉得文笔还可以，请点个关注点个赞。公众号《书所集录》同步更新，也欢迎大家关注点赞。
