My concise C++ solution


  • 2
    O

    It seems we have to have another round of getting result after the DP search (to not exceed memory limit). Here I inserted spaces to the original string instead of constructing strings.

    vector<string> wordBreak(string s, unordered_set<string> &dict)
    {
    	vector<vector<int>> flag(s.size() + 1, vector<int>());
    	flag[0].push_back(0);
    	for (int i = 1; i <= s.size(); i++)
    	{
    		for (int j = 0; j < i; j++)
    		{
    			if (!flag[j].empty() && dict.find(s.substr(j, i - j)) != dict.end())
    			{
    				flag[i].push_back(j);
    			}
    		}
    	}
    	vector<string> result;
    	getResult(result, flag, s, s.size());
    	return result;
    }
    
    void getResult(vector<string> &result, vector<vector<int>> &flag, string s, int n)
    {
    	for (int i : flag[n])
    	{
    		if (i == 0)
    		{
    			result.push_back(s);
    			continue;
    		}
    		s.insert(s.begin() + i, ' ');
    		getResult(result, flag, s, i);
    		s.erase(i, 1);
    	}
    }

  • 0
    O

    such a beautiful solution


Log in to reply
 

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