Python中的断字
假设我们有一个非空字符串s和一个字典wordDict。那包含一个非空单词的列表，确定何时可以将s分割成一个或多个字典单词的以空格分隔的序列。我们必须遵循一些规则-
字典中的同一单词可以在分割中多次重复使用。
我们可以假设字典中不包含重复的单词。
假设字符串s=“applepenapple”，并且单词字典类似于[“apple”，“pen”]，则输出为true，因为字符串s可以分段为“applepenapple”。
让我们看看步骤-
定义一个nxn阶的矩阵DP。n=字符串的大小，并使用false对其进行初始化
对于范围1到s长度的i
如果字典中的子字符串s[j至j+1]，则dp[j，j+i-1]：=True
除此以外
如果dp[j，k-1]和dp[k，j+i–1]，则dp[j，j+i–1]：=True
对于范围j+1至j+i的k
对于0到s长度范围内的j–i
返回DP[0，s的长度-1]
示例(Python)
让我们看下面的实现以更好地理解-
class Solution(object):
def wordBreak(self, s, wordDict):
dp = [[False for i in range(len(s))] for x in range(len(s))]
for i in range(1,len(s)+1):
for j in range(len(s)-i+1):
#print(s[j:j+i])
if s[j:j+i] in wordDict:
dp[j][j+i-1] = True
else:
for k in range(j+1,j+i):
if dp[j][k-1] and dp[k][j+i-1]:
dp[j][j+i-1]= True
return dp[0][len(s) - 1]
ob1 = Solution()print(ob1.wordBreak("applepenapple", ["apple", "pen"]))输入值
"applepenapple" ["apple", "pen"]
输出结果
true