Simple C++ Solution


  • 0
    J

    '''

    bool wordBreak(string s, unordered_set<string>& wordDict) {
        int n = s.size();
        if (!n) return true;
        vector<bool> f(n + 1, false);
        f[0] = true;
    
        int maxLen = 0, minLen = INT_MAX;
        for (string word : wordDict)
        {
            int len = word.size();
            maxLen = max(maxLen, len);
            minLen = min(minLen, len);
        }
        
        for (int i = 1; i <= n; i++)
        {
            for (int j = minLen; j <= min(maxLen, i); j++)
            {
                if (f[i - j])
                {
                    string word = s.substr(i - j, j);
                    if (wordDict.count(word))
                    {
                        f[i] = true;
                        break;
                    }
                }
            }
        }
        
        return f[n];
    }
    

    '''


Log in to reply
 

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