Leetcode 140 Word Break II

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;  
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏公众号_薛勤的博客

Jsoup模拟登录带验证码的教务系统(原理详解)

在模拟登陆该教务系统时,笔者观察到该教务系统还有一个不需要验证码即可登陆的网址:http://jwxt.qlu.edu.cn/jsxsd/xsxk/xklc_l...

19620
来自专栏计算机视觉与深度学习基础

Leetcode 274. H-Index

Given an array of citations (each citation is a non-negative integer) of a rese...

35080
来自专栏武培轩的专栏

猫眼面经汇总

java.util.Collections 是一个包装类(工具类/帮助类)。它包含有各种有关集合操作的静态多态方法。此类不能实例化,就像一个工具类,用于对集合中...

19430
来自专栏步履前行

Java 基础-LocalDate相关

那么在写具体的LocalDate前,我们先来看下为什么要在Java8中搞一套新的API呢,因为旧的Date类非常的难用,比如,其中的几个构造方法都被标注为@De...

59010
来自专栏IT杂记

DateFormat 线程不安全

一、测试 测试代码如下:  private static SimpleDateFormat sdf = new SimpleDateFormat("yy...

21950
来自专栏linux驱动个人学习

Linux内存描述之内存节点node--Linux内存管理(二)

这点前面是说的很明白了, NUMA结构下, 每个处理器CPU与一个本地内存直接相连, 而不同处理器之前则通过总线进行进一步的连接, 因此相对于任何一个CPU访问...

49220
来自专栏偏前端工程师的驿站

Java魔法堂:Date与日期时间格式化

一、前言                                                                            ...

26680
来自专栏Linux技术资源分享

数据库Dao层抽象出BasicDao类 | 许久没碰Java了、致Java初学者

19240
来自专栏Linyb极客之路

编码习惯之参数校验和国际化规范

今天我们说说参数校验和国际化,这些代码没有什么技术含量,却大量充斥在业务代码上,很可能业务代码只有几行,参数校验代码却有十几行,非常影响代码阅读,所以很有必要把...

32760
来自专栏Android 研究

OKHttp源码解析(七)--中阶之缓存机制

Entry内部类是实际用于存储的缓存数据的实体类,每一个url对应一个Entry实体

24360

扫码关注云+社区

领取腾讯云代金券