Word Break II in Python

Suppose we have a non-empty string s and a dictionary called wordDict, this dictionary is containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. We have to find all such possible sentences. “appleraincoat” and dictionary is [“app”, “apple”, “rain”, “coat”, “raincoat”]

To solve this, we will follow these steps −

• Create one map memo

• Define a method called solve, this will take string and wordDict

• if s is null, then return empty list

• if s in memo, then −

  • return memo[s]

• create an array ret

• for i in range 1 to size of s

  • if substring of s from index 0 to i – 1 present in wordDict, then

    • for j in solve(substring of s from i to end, wordDict)

    • p := substring of s from index 0 to i – 1, concatenate with space and j, then clear extra space from left and right −

    • insert p into ret

• memo[s] := ret

• return memo[s]

Example

Let us see the following implementation to get better understanding −

 Live Demo

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"]))

Input

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

Output

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