Sharing my 12ms C++ solution using DP


  • 0
    T
    class Solution {
    public:
        bool wordBreak(string s, unordered_set<string>& wordDict) {
            int n = s.length();
            vector<bool> DP(n+1, false);
            // dynamic programming
            DP[0] = true;
            int i, j;
            string substr;
            for(i=1; i<=n; i++)
            {
                for(j=0; j<i; j++)
                {
                    substr = s.substr(j, i-j);
                    if(wordDict.find(substr) != wordDict.end())
                    {
                        DP[i] = DP[j];
                        if(DP[i])
                            break;
                    }
                }
            }
            
            return DP[n];
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.