Leetcode Problem 140 Word Break II.txt

140. Word Break II
Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences.

Note:

The same word in the dictionary may be reused multiple times in the segmentation.
You may assume the dictionary does not contain duplicate words.
Example 1:

Input:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
Output:
[
  "cats and dog",
  "cat sand dog"
]
Example 2:

Input:
s = "pineapplepenapple"
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
Output:
[
  "pine apple pen apple",
  "pineapple pen apple",
  "pine applepen apple"
]
Explanation: Note that you are allowed to reuse a dictionary word.
Example 3:

Input:
s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]
Output:
[]


Hint to solve: Use dynamic programming to check if the string can be spit. Create one more list of list and record where the split was true. Recurse on this list of list and construct the sentences again.


class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        
        dpArray = [False]*(len(s)+1)
        indexArray = [[] for _ in range(0, len(s)+1)]
        dpArray[0] = True
        
        
        for length in range(1, len(dpArray)):
            for temp in range(0, length):
                if(dpArray[temp] == True and s[temp:length] in wordDict):
                    dpArray[length] = True
                    indexArray[temp].append(length-temp)
                    
        #print(indexArray)
        #If we can't split the given string from the keys in dictionary then just remove them
        if(dpArray[len(s)] == False):
            return []
        
        result = []
        def constructSentences(index, currentString):
            #print(index, ' ', currentString)
            #If the current index has reached the end then remove the last character(extra white space) and append result
            if(index == len(s)):
                result.append(currentString[:-1])
            
            original = currentString
            
            #Make recursive call and jump to next index
            for x in indexArray[index]:
                currentString = original + s[index:(index+x)] + " "
                #print("making recursive call to index: ", x)
                constructSentences(index + x, currentString)
        
        constructSentences(0,'')
        
        return result