word break

class Solution {
public:

    bool fun (string &s, unordered_map < string , bool> &str_dir, int begin, vector <int> &dp)
    {

        if (begin == s.size())
            return true;

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

        for (int end = begin ; end < s.size(); end ++)
        {



            if ( str_dir.count(s.substr(begin, end - begin + 1)) != 0 && fun (s, str_dir, end + 1, dp))
            {

                 dp[begin] = true;
                return true;

            }
        }

         dp[begin] = false;
                    return false;

    }
    bool wordBreak(string s, vector<string>& wordDict) {

        vector <int> dp (s.size(), -1);
        unordered_map < string , bool> str_dir;

        for (auto cur : wordDict)
        {
            str_dir[cur] = true;
        }

       if (str_dir.size() == 0) return false;
        return fun (s, str_dir, 0, dp);
    }
};


/*



*/