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

  • 1
    class Solution
        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.