Share my 8ms c++ solution


  • 1
    C

    I took advantage of the result from the problem 'word break', saving a dp table to help avoid repeating searches.

    class Solution 
    {
    public:
        vector<string> wordBreak(string s, unordered_set<string>& wordDict) 
        {
           /******** Below is the result form word break **********/
            vector<bool> dp(s.size() + 1, false);
            dp[0] = true;
    
            for (int i = 1; i <= s.size(); ++i)
                for (int j = i - 1; j >= 0 && !dp[i]; --j)
                    dp[i] = dp[j] && wordDict.find(s.substr(j, i - j)) != wordDict.end();
            if(!dp[s.size()]) return {};
            /******************************************************/
            vector<string> ret;
            wordBreak(s, 0, wordDict, dp, "", ret);
            return ret;
        }
        
        void wordBreak(const string &s, int beg, unordered_set<string> &wordDict, vector<bool> &dp, string str, vector<string> &ret)
        {
            if(beg == s.size())
            {
                ret.push_back(str.substr(0, str.size() - 1));  //eliminate the last space
                return;
            }
            
            for(int i = beg + 1; i <= s.size(); ++i)
             //We only go further for certain cases
                if(dp[i] && wordDict.find(s.substr(beg, i - beg)) != wordDict.end()) 
                    wordBreak(s, i, wordDict, dp, str + s.substr(beg, i - beg) + " ", ret);
        }
    };

  • 0

    好棒啊..最后是用了一个回溯法么???????????????????


  • 0
    C

    第一步是一个动态规划,你可以先看看word break I,第二步是回溯法


Log in to reply
 

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