Python中的断字

假设我们有一个非空字符串s和一个字典wordDict。那包含一个非空单词的列表，确定何时可以将s分割成一个或多个字典单词的以空格分隔的序列。我们必须遵循一些规则-

• 字典中的同一单词可以在分割中多次重复使用。

• 我们可以假设字典中不包含重复的单词。

假设字符串s =“ applepenapple”，并且单词字典类似于[“ apple”，“ pen”]，则输出为true，因为字符串s可以分段为“ apple pen apple”。

让我们看看步骤-

• 定义一个nx n阶的矩阵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