Word break

'''
Logic:
1.We pushed all the words into the map so that we can search words in O(1) time.
2.We are iterating through the string from the begining and if we get that string present
  in map,we pass the further string in same function.If we get output as 1 means that
  current break is possible.so we make our dp for that index as 1.
3.Before iterating,if we already have 0 or 1 output,means we have already tried to break
  from here.so return that output.

Basicaly,DP[i] represents that String can be broken from ith position or not,for that if
string after that can be broken,only then it is possible.
'''
def fun(str,l,dict,dp):
    if l==len(str): #l==len(str) only when all the previous chars are already in the word dictionary
        return True
    if dp[l] is not None:
        return dp[l]
    for i in range(l,len(str)):
        if str[l:i+1] in dict and fun(str,i+1,dict,dp):
            dp[l]=True
            return dp[l]
    dp[l]=False
    return dp[l]


class Solution:
    def wordBreak(self, s: str, dict: List[str]) -> bool:
        dp=[None]*len(s) #here None is mandatory so that we can know while returning dp[l] before for loop that has it been gone in recursion or not else if False we will keep,everytime we will return True even though some split is false
        return fun(s,0,dict,dp)