题目链接

单词拆分

题目描述

image.png

实现代码

动态规划思想：记dp[i]表示在字符串的前i个字符时是否能够进行单词拆分；

对于一个长度为i的字符串，能否被已知的几个字符串组合，就看它每个切分点切分后的子串是否在已知的字符串列表中，遍历字符串，每个点都做为切分点，判定字符串能被拆分需要同时满足下列两个条件：

  1. 切分点j的前j个字符组成的字符串能被正确拆分；
  2. 切分点j的后j到i的字符组成的字符串存在于一直的字符串列表中；

实现代码如下：

  1. class Solution:
  2.     def wordBreak(self, s: str, wordDict: List[str]) -> bool:
  3.         n = len(s)
  4.         dp = [True] + [False for _ in range(n)]
  6.         for i in range(1, n+1):
  7.             for j in range(0, i):
  8.                 if dp[j]:
  9.                     sub = s[j:i]
  10.                     if sub in wordDict:
  11.                         dp[i] = True
  12.                         break
  13.         return dp[n]