16ms C++ DP solution


  • 0
    J
    class Solution {
    public:
        bool wordBreak(string s, unordered_set<string>& wordDict) {
            int len = s.size();
            if(len == 0) return false;
            set<int> tmp;
            
            for(int i = 0; i < len; ++i) {
                if(wordDict.find(s.substr(0,i + 1)) != wordDict.end()) {
                    tmp.insert(i);
                    continue;
                }
                for(set<int>::iterator it = tmp.begin(); it != tmp.end(); ++it) {
                    if(wordDict.find(s.substr((*it) + 1, i - (*it))) != wordDict.end()) {
                        tmp.insert(i);
                        break;
                    }
                }
            }
            if(tmp.find(len - 1) != tmp.end()) return true;
            else return false;
        }
    };

Log in to reply
 

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