Leetcode 140 Word Break II

triplebee

发布于 2018-01-12 14:53:03

4660

发布于 2018-01-12 14:53:03

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given s = "catsanddog", dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].

和上一题一样，如果直接在dp的过程中记录路径，会MLE，因为存储了许多不必要的中间结果。

在一开始MLE的基础上，我做了一点优化，与之前单词梯的方法类似，先记录前驱节点，这样比直接记大量字符串节省空间，最后dfs跑一边结果。

class Solution {
public:
    void dfs(vector<string> &res, string now, vector<vector<int>>& dp, int index, string& s)
    {
        if (index == 0)
        {
            now = now.substr(0, now.size()-1);
            res.push_back(now);
            return ;
        }
        for(int i = 0; i < dp[index].size(); i++)
        {
            dfs(res, s.substr(dp[index][i], index - dp[index][i])+" "+ now, dp, dp[index][i], s);
        }
    }
    vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
        vector<int> temp;
        vector<vector<int>> dp(s.size()+1, temp);  
        dp[0].push_back(0);  
        for (int i = 1; i<= s.size(); i++)  
        {  
            for(int j = 0; j < i; j++)  
            {  
                if(dp[j].empty()) continue;  
                if(wordDict.find(s.substr(j, i-j)) != wordDict.end()) dp[i].push_back(j);
            }  
        }
        vector<string> res;
        string now;
        dfs(res, now, dp, s.size(), s);
        return res;  
    }
};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2016-11-17 ，如有侵权请联系 cloudcommunity@tencent.com 删除

add