C++ 4ms Easy to Understand DP code with Explanation. Mine looks a bit different from other DP


  • 1
    W
    class Solution
    {
    public:
        bool wordDP(string s, unordered_set<string>& wordDict, int startIndex, vector<bool>& isDone, int longestWordSize)
        {
            // startIndex reached the end. It is breakable.
            if (startIndex == s.size()) return true;
            // The string starting at startIndex has been checked but didn't return true
            // This means the string starting at this startIndex is NOT breakable
            if (isDone[startIndex]) return false;
            
            for (int i = 1; i <= longestWordSize; i++)
            {
                // For each of the substring starting at startIndex with length i
                // Check if that substring exists in the wordDict.
                // If it does, recurse into this function with new startIndex starting from startIndex+i, 
                // until it reaches the end or until there is no substring that matches a string in wordDict
                auto subWord = s.substr(startIndex, i);
                if (wordDict.count(subWord) != 0)
                {
                    // If found out that it is breakable, return true. 
                    // Don't need to any more work
                    if (wordDP(s, wordDict, startIndex + i, 
                               isDone, longestWordSize))
                        return true;
                }
            }
            
            // The string starting at startIndex is checked but is not breakable
            isDone[startIndex] = true;
            return false;
        }
        bool wordBreak(string s, unordered_set<string>& wordDict) 
        {
            // don't need anything longer than this
            int longestWordSize = 0;
            for (auto it = wordDict.begin(); it != wordDict.end(); it++)
                longestWordSize = max((int)it->size(), longestWordSize);
            
            // memoizing whether the string starting at index is already checked
            vector<bool> isDone(s.size(), false);
            return wordDP(s, wordDict, 0, isDone, longestWordSize);
        }
    };

Log in to reply
 

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