class Solution {
private:
    vector<int> word_len;
    int s_len;
    vector<int> dp;
public:
    void solve(string& s, int idx, vector<string>& wordDict)
    {
        if (idx >= s_len)
        {
            dp[s_len] = 1;
            return;
        }

        if (dp[idx] != -1)
            return;

        for (int i = 0; i < wordDict.size(); i++)
        {
            if (s.compare(idx, word_len[i], wordDict[i]) == 0)
            {
                solve(s, idx + word_len[i], wordDict);
                if (dp[s_len] == 1)
                    return;
            }
        }

        dp[idx] = 0;
    }

    bool wordBreak(string s, vector<string>& wordDict) {
        word_len.resize(wordDict.size(), 0);
        s_len = s.length();
        dp.resize(s_len + 1, -1);
        dp[s_len] = 0;

        for (int i = 0; i < wordDict.size(); i++)
        {
            word_len[i] = wordDict[i].length();
        }

        solve(s, 0, wordDict);
        return dp[s_len];
    }
};