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

Arnab Chakraborty

更新日期： 28-Apr-2020

844 次瀏覽

開啟你的 職業生涯

完成課程即可獲得認證

開始