WordBreak.cpp

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        if (s.empty())
        {
            return false;
        }
        if (wordDict.empty())
        {
            return false;
        }
        std::size_t minLen = 0;
        for (const std::string& word: wordDict)
        {
            minLen = std::min(word.size(), minLen);
            if (s == word)
            {
                return true;
            }
            std::size_t pos = s.find(word);
            while (pos != std::string::npos)
            {
                dp[pos][word.size()] = true;
                pos = s.find(word, pos + 1);
            }
        }
        if (s.size() < 2 * minLen)
        {
            return false;
        }
        
        for (int i = 0; i < s.size(); ++i)
        {
            for (int j = minLen * 2; j <= s.size() - i; ++j)
            {
                for (int k = minLen; k < j; ++k)
                {
                    const bool breakable = dp[i][k] && dp[k][j - k];
                    if (breakable)
                    {
                        dp[i][j] = true;
                        break;
                    }
                }
            }
        }
        
        return dp[0][s.size()];
    }
    
    private:
    bool dp[1000][1000]{};
};