//Approach-1: Memoization DP
class Solution {
    int dp[305];
    unordered_set<string> st;//dictionary
    int fun(int i, string s){
        if(i==s.size())   return true;
        if(dp[i]!=-1)  return dp[i];

        for(int j=i;j<s.size();j++)
            if(st.count(s.substr(i,j-i+1)) && fun(j+1,s))
                return dp[i] = 1;
        return dp[i] = 0;
    }
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        memset(dp,-1,sizeof(dp));
        for(string& x: wordDict)
            st.insert(x);

        return fun(0,s)==1?true:false;
    }
};