class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {

        int n = s.size();
        bool dp[n+1]={0};

        set<string> st(wordDict.begin(), wordDict.end());
        dp[0] = true;

        for(int i=1;i<=n;i++)
        {

            for(int j=0;j<i;j++)
            {
                string check = s.substr(j, i-j);
                if(dp[j] && (st.find(check)!=st.end()))
                {
                    dp[i] = true;
                    break;
                }
            }
        }

        return dp[n];

    }
};