Python 中的单词拆分

假设我们有一个非空字符串 s 和一个字典 wordDict。其中包含一个非空词语表，请确定 s 是否可以分隔成空格分隔的一个或多个字典词语序列。我们必须遵循一些规则 −

  • 字典中的同个词语可以在分隔中重复使用多次。
  • 我们可以假设字典中没有重复的词语。

假设字符串 s = “applepenapple”，词典为 [“apple”， “pen”]，则输出为 true，因为字符串 s 可以分隔为“apple pen apple”。

让我们来看一下步骤 −

  • 定义一个 n x n 顺序的矩阵 DP。n = 字符串的长度，并将其初始化为 false。
  • 对于 s 的长度从 1 到 n 的值域
    • 对于 s 的长度从 0 到 s 的长度 – i 的值域
      • 如果子串 s[j 到 j + 1] 在字典中，则 dp[j, j+i - 1] := True
      • 否则
        • 对于 k 从 j + 1 到 j + i 的值域
          • 如果 dp[j, k - 1] 和 dp[k, j + i – 1]，则 dp[j, j + i – 1] := True
  • 返回 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

更新日期： 28-Apr-2020

844 次浏览

开启你的 职业生涯

完成课程即可获得认证

开始
广告