8ms C++ Solution, dp and recursion


  • 0

    I use quite a few vectors and sets, trying to speed up the calculation.

    class Solution {
    private:
        void split( vector<bool>& dp, unordered_set<string>& wordDict, unordered_set<int>& lenset, 
            int index, string& s, vector<string>& ans, vector<string>& buf ) {
            for( int len : lenset ) {
                if( len > s.length() - index ) continue;
                if( !dp[index + len] ) continue;
                string sub = s.substr( index, len );
                if( wordDict.find(sub) == wordDict.end() ) continue;
                buf.push_back(sub);
                if( len == s.length() - index ) {
                    string tmp = buf[0];
                    for( int i=1; i<buf.size(); i++ ) {
                        tmp.append(" ");
                        tmp.append(buf[i]);
                    }
                    ans.push_back(tmp);
                } else split( dp, wordDict, lenset, index + len, s, ans, buf );
                buf.pop_back();
            }
        }
    public:
        vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
            vector<string> ans, buf;
            vector<bool> dp(s.length()+1);
            dp[0] = true;
            for( int i=1; i<s.length()+1; i++ ) {
                for( int j=i-1; j>=0; j-- ) {
                    if( dp[j] && wordDict.find(s.substr(j,i-j)) != wordDict.end() ) {
                        dp[i] = true;
                        break;
                    }
                }
            } 
            if( !dp[s.length()] ) return ans;
            unordered_set<int> lenset;
            for( string str : wordDict ) lenset.insert(str.length());
            split(dp, wordDict, lenset, 0, s, ans, buf);
            return ans;
        }
    };

Log in to reply
 

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