C++ solution based on DP


  • 0
    B
    class Solution {
    public:
        bool wordBreak(string s, vector<string>& wordDict) {
            unordered_set<string> dictSet;
            unordered_set<int> lengthSet;
            int maxLength = 0;
            for (auto w : wordDict) {
                if (lengthSet.find(w.length()) == lengthSet.end()) {
                    lengthSet.emplace(w.length());
                }
    
                dictSet.emplace(w);
            }
    
            vector<bool> cache(s.length(), false);
    
            for (int i = s.length() -1; i >= 0;i--) {
                bool result = false;
                for (auto iterator = lengthSet.begin(); iterator != lengthSet.end(); iterator++) {
                    int length = *iterator;
                    if (dictSet.find(s.substr(i, length)) != dictSet.end()) {
                        if (i + length < s.length() && cache[i + length]) {
                            result = true;
                            break;
                        }
                        else if (i + length == s.length())
                        {
                            result = true;
                            break;
                        }
                    }
                }
    
                cache[i] = result;
            }
    
            return cache.front();
        }
    };
    

Log in to reply
 

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