[Word Break II] I got a Runtime error with a DP solution but it works on visual studio 2008


  • 0
    S

    [Word Break II] I got a Runtime error with a DP solution but it works on visual studio 2008

    Last executed input: "a", ["a"]

    DP[i] means a substring with end pos i could be breaked into words or not

    strs stores all vectors<string> with different length

    tmpResult stores the sub strings breaked into words with end pos i

    here is my code

    class Solution
    {
    public:
    	vector<string> wordBreak(string s, unordered_set<string> &dict)
    	{
    		int len = s.size();
            vector<vector<string>>  strs(len + 1, vector<string>());
    		vector<bool> DP(len + 1, false);
    		DP[0] = true;
    
    		for(int i = 0; i < len; ++i)  // end pos of a sub string
    		{
    			vector<string> tmpResult;
    			for(int j = i; j >= 0; --j)  // start pos of a sub string
    			{
    				string str = s.substr(j, i - j + 1);
    				if(dict.find(str) != dict.end() && DP[j]) 
    				{
                        if(j == 0)
    					{
    						if(i != len - 1)
    						    str.append(" ");
    						tmpResult.push_back(str);  // start words
    					}
    					else
    					{
    						// append each word to its previous string
    						for(int index = 0; index < strs[j].size(); ++index)
    						{
    							string tmpStr = strs[j][index];
    							tmpStr.append(str);
    							if(i != len - 1)
    							    tmpStr.append(" ");
    							tmpResult.push_back(tmpStr);
    						}
    					}
    	
    					DP[i + 1] = true;
    				}
    			}
    
    			if(DP[i + 1])
    			    strs[i + 1] = tmpResult;  // update
    		}
    
    		if(DP.at(len))
                return strs.at(len);
    	}
    };

Log in to reply
 

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