PythonのWordBreakII

空でない文字列sとwordDictという辞書があるとします。この辞書には空でない単語のリストが含まれており、sにスペースを追加して、各単語が次のような文を作成します。有効な辞書の単語。そのような可能な文をすべて見つけなければなりません。 「appleraincoat」と辞書は[「app」、「apple」、「rain」、「coat」、「raincoat」]

これを解決するには、次の手順に従います-

• マップメモを1つ作成する

• 解決と呼ばれるメソッドを定義します。これには文字列とwordDictが必要です

• sがnullの場合、空のリストを返します

• メモにsがある場合、-

  • メモを返す

• 配列を作成するret

• 1からsのサイズまでの範囲のiの場合

  • インデックス0からi– 1までのsのサブストリングがwordDictに存在する場合、

    • ソルブのjの場合（iからendまでのsの部分文字列、wordDict）

    • p：=インデックス0からi – 1までのsの部分文字列で、スペースとjを連結してから、左右から余分なスペースをクリアします-

    • pをretに挿入

• memo [s]：=ret

• メモを返す

例

理解を深めるために、次の実装を見てみましょう-

class Solution(object):
   def wordBreak(self, s, wordDict):
      self.memo = {}
      wordDict = set(wordDict)
      return self.solve(s,wordDict)
   def solve(self,s, wordDict):
      if not s:
         return ['']
      if s in self.memo:
         return self.memo[s]
      ret = []
      for i in range(1,len(s)+1):
         if s[:i] in wordDict:
            for j in self.solve(s[i:],wordDict):
               ret.append((s[:i] + " " + j).strip())
      self.memo[s] = ret
      return self.memo[s]

ob = Solution()
print(ob.wordBreak("appleraincoat",["app","apple","rain","coat","rain coat"]))

入力

"appleraincoat"
["app","apple","rain","coat","raincoat"]

出力

['apple rain coat', 'apple raincoat']