Pythonでのワードブレイク

• 辞書内の同じ単語は、セグメンテーションで複数回再利用される可能性があります。
• 辞書に重複する単語が含まれていないと想定できます。

文字列s=“ applepenapple”で、単語辞書が[“ apple”、“ pen”]のようなものであるとすると、文字列sは“ apple pen apple”としてセグメント化できるため、出力はtrueになります。

手順を見てみましょう-

• 次数nxnの1つの行列DPを定義します。 n =文字列のサイズ、falseで初期化
• 1からsの長さまでのiの場合
  • 範囲0からsの長さのjの場合– i
    • 辞書に部分文字列s[jto j + 1]がある場合、dp [j、j + i --1]：=True
    • それ以外の場合
      • j+1からj+iの範囲のkの場合
        • dp [j、k-1]およびdp [k、j + i – 1]の場合、dp [j、j + i – 1]：=True
• return DP [0、length 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