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.
*/

unordered_map<string,int> mp;
int fun(string s,int l,int dp[]){
    if(l==s.size()) return 1;
    if(dp[l]!=-1) return dp[l];
    for(int i=l;i<s.size();i++){
        if(mp[s.substr(l,i-l+1)] && fun(s,i+1,dp)==1){ dp[l]=1;return dp[l];}
    }
    dp[l]=false;
    return dp[l];
}
class Solution {
public:
    bool wordBreak(string s, vector<string>& word){
        mp.clear();
        for(auto itr:word) mp[itr]++;
        int dp[s.size()+1];
        memset(dp,-1,sizeof(dp));
        if(fun(s,0,dp)==1) return true;
        else return false;
    }
};