【面试经典 | 150】单词拆分

文章目录

  • Tag
  • 题目来源
  • 解题思路
    • 方法一:动态规划
  • 写在最后

Tag

【动态规划】【字符串】


题目来源

139. 单词拆分


解题思路

方法一:动态规划

定义状态

定义 dp[i] 表示字符串 si 个字符组成的字符串(s[0, ..., i-1])是否能被空格拆分成若干个在字典中出现的单词。

转移关系

dp[i]dp[j] 以及字符串 s[j, i-1] 有关,即有

KaTeX parse error: Expected 'EOF', got '&' at position 16: dp[i] = dp[j] &̲ check(s.substr…

其中 check() 表示判断参数是否在 wordDict 字符串列表中。

base case

dp[0] = true,表示初始状态即空字符串也在 wordDict 字符串列表中。

最后返回

最后返回 dp[s.size()],即使用 wordDict 字符串列表中的一个或多个单词是否可以拼接出字符串 s

实现代码

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> st;
        for (const auto& word : wordDict) {
            st.insert(word);
        }

        int n = s.size();
        vector<bool> dp(n+1);
        dp[0] = true;
        for (int i = 1; i < n+1; ++i) {
            for (int j = 0; j < i; ++j) {
                if (dp[j] && st.find(s.substr(j, i-j)) != st.end()) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }
};

复杂度分析

时间复杂度: O ( n ) O(n) O(n) n n n 为字符串 s 的长度。我们一共有 O ( n ) O(n) O(n) 个状态需要计算,每次计算需要枚举 O ( n ) O(n) O(n) 个分割点,哈希表判断一个字符串是否出现在给定的字符串列表需要 O ( 1 ) O(1) O(1) 的时间,因此总时间复杂度为 O ( n 2 ) O(n^2) O(n2)

空间复杂度: O ( n ) O(n) O(n)


写在最后

如果您发现文章有任何错误或者对文章有任何疑问,欢迎私信博主或者在评论区指出 💬💬💬。

如果大家有更优的时间、空间复杂度的方法,欢迎评论区交流。

最后,感谢您的阅读,如果有所收获的话可以给我点一个 👍 哦。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/496597.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

7.JDK下载和安装

文章目录 一、下载二、安装三、JDK的安装目录介绍 写JAVA代码不是随随便便能写的&#xff0c;我们得先做一点准备工作。例如&#xff0c;我们平时想要玩一把游戏&#xff0c;就需要先下载、安装才能玩游戏。JAVA也是一样的&#xff0c;也是需要下载并安装相关的软件&#xff0c…

2010-2021年银行网点及员工信息数据

2010-2021年银行网点及员工信息数据 1、时间&#xff1a;2010-2021年 2、来源&#xff1a;整理自csmar 3、指标&#xff1a;银行代码、股票代码、银行中文简称、统计截止日期、分行数量、机构网点数量、其中&#xff1a;境内网点数量、其中&#xff1a;境外网点数量、在职员…

[疑难杂症2024-002]一个“显而易见“的问题,是如何进入生产环境的?

本文由Markdown语法编辑器编辑完成。 1. 前言 最近在处理一个在医院上线的系统的问题。这个问题&#xff0c;由于关联的模块比较多&#xff0c;至少涉及到3个模块之间的功能调用。因此&#xff0c;协调大家都有时间来排查问题不是很方便。这个问题就拖了有一周左右。医院那边…

2024-03-28 Quest3 开发环境配置教程

文章目录 准备条件1 登录 Meta 账号2 Oculus 软件下载与配置3 下载 Quest3 开发包4 Unity 环境配置环境测试 准备条件 Quest3 头显一个。一根 USB 3.0 数据线。魔法。 ​ 有关 quest3 激活与配置可参考 B 站 UP &#xff1a;“南七月nqy_”。跳转链接&#xff1a;https://spa…

Exception in thread “main“ com.fasterxml.jackson.databind.JsonMappingException:

问题&#xff1a;jaskson反序列化超出最大长度 Caused by: com.fasterxml.jackson.core.exc.StreamConstraintsException: String length (5043456) exceeds the maximum length (5000000) 场景&#xff1a;前端传递过大base64 原因&#xff1a; jaskon默认已经限制了最大长…

货币系统(闫氏DP分析法)

题目描述&#xff1a; 给定 V 种货币&#xff08;单位&#xff1a;元&#xff09;&#xff0c;每种货币使用的次数不限。 不同种类的货币&#xff0c;面值可能是相同的。 现在&#xff0c;要你用这 V 种货币凑出 N 元钱&#xff0c;请问共有多少种不同的凑法。 输入格式&am…

路由的完整使用

多页面和单页面 多页面是指超链接等跳转到另一个HTML文件,单页面是仍是这个文件只是路由改变了页面的一部分结构. 路由的基本使用 使用vue2,则配套的路由需要是第3版. 1)下载vue-router插件 2)引入导出函数 3)new 创建路由对象 4)当写到vue的router后只能写路由对象,因此只…

CImage 类及其常用成员函数用法实例详解 一

Cimage类是一个用于处理图像的类&#xff0c;它的主要用途是方便地创建、编辑、保存和显示图像。Cimage类支持多种图像文件格式&#xff0c;包括BMP、GIF、JPG、PNG和TIF等。较CBitmap类使用起来更方便。其构造函数及成员函数如下&#xff1a; 下面详细说明CImage常用成员函数的…

解决Animate.css动画效果无法在浏览器运行问题

背景 在开发官方网站的时候&#xff0c;临时更换了电脑&#xff0c;发现原本正常的动画效果突然不动了。 经过 chrome、Microsoft Edge都无法运行。 Animate.css | A cross-browser library of CSS animations. 问题排查 通过审查元素后发现类名是注入并且生效的。 验证 然…

【漏洞复现】企互联-FE企业运营管理平台uploadAttachmentServlet接口存在任意文件上传漏洞

漏洞描述 FE企业运营管理平台(以下简称FE6.5)是基于互联企业云工作台,以移动技术、云计算、大数据处理技术、传感技术等信息技术为支撑,和各类业务系统全面融合的移动化云平台,分为企业版和集团版,能满足各种规模企业的信息化建设需求。FE6.5以移动、平台、社交、云及大…

OpenHarmony实战开发-List组件的使用之设置项

介绍 在本篇CodeLab中&#xff0c;我们将使用List组件、Toggle组件以及Router接口&#xff0c;实现一个简单的设置页&#xff0c;点击将跳转到对应的详细设置页面。效果图如下&#xff1a; 相关概念 CustomDialog&#xff1a;CustomDialog装饰器用于装饰自定义弹窗。List&…

Apifox 新版发布:多分支升级、Query 参数支持枚举、自定义快捷键全面解读

看看本次版本更新主要涵盖的重点内容&#xff0c;有没有你所关注的功能特性&#xff1a; 多分支能力持续升级Query 参数支持枚举等高级配置支持自定义快捷键支持全局设置是否允许返回响应里有额外字段支持导入非 API 的 Markdown 文件更多 CI/CD 平台集成环境变量支持实时协作…

基于springboot+vue+Mysql的“智慧食堂”设计与实现

开发语言&#xff1a;Java框架&#xff1a;springbootJDK版本&#xff1a;JDK1.8服务器&#xff1a;tomcat7数据库&#xff1a;mysql 5.7&#xff08;一定要5.7版本&#xff09;数据库工具&#xff1a;Navicat11开发软件&#xff1a;eclipse/myeclipse/ideaMaven包&#xff1a;…

查找总价格为目标值的两个商品【双指针】

这道题实际上跟本专栏上一题属于同一类型&#xff0c;是上一题的简单版&#xff0c;可以点击跳跃。 ⬇ 有效三角形的个数【双指针】 法一&#xff1a;暴力求解 class Solution { public:vector<int> twoSum(vector<int> &nums, int target){int n nums.size()…

Numpy 初体验

文章目录 第1关&#xff1a;Numpy 创建数组第2关&#xff1a;Numpy 数组的基本运算第3关&#xff1a;Numpy 数组的切片与索引第4关&#xff1a;Numpy 数组的堆叠第5关&#xff1a;Numpy 的拆分 第1关&#xff1a;Numpy 创建数组 编程要求 本关的任务是&#xff0c;补全右侧编辑…

用docker在局域网虚拟一个docker虚拟机,支持单独ip,gpu,systemd,在docker里面安装docker

可以实现局域网内虚拟一台linux服务器&#xff0c;效果类似虚拟机&#xff0c;用docker实现&#xff0c;需要注意&#xff0c;这种方式和宿主机是不能通讯的&#xff0c;但是可以和局域网内的设备通讯 觉得好用可以加作者wx: lx-ivan 编写dockerfile vim Dockerfile FROM u…

飞鸟写作怎么用 #经验分享#学习方法#学习方法

飞鸟写作是一款非常好用的论文写作工具&#xff0c;它不仅能够帮助用户写作论文&#xff0c;还可以检测论文的原创性和查重率&#xff0c;是许多学生和研究人员的首选工具。 使用飞鸟写作非常方便&#xff0c;用户只需将论文复制粘贴到工具中&#xff0c;就能够快速得到论文的原…

【Hello,PyQt】控件拖拽

在 PyQt 中实现控件拖拽功能的详细介绍 拖拽功能是现代用户界面设计中常见的交互方式之一&#xff0c;它可以提高用户体验&#xff0c;增加操作的直观性。在 PyQt 中&#xff0c;我们可以很容易地实现控件之间的拖拽功能。本文将介绍如何在 PyQt 中实现控件的拖拽功能。 如何实…

初识C++ · 入门(1)

目录 前言&#xff1a; 1 命名空间 2 输入和输出 3 缺省参数 5 函数重载 前言&#xff1a; C与C语言是有一定交集的&#xff0c;可以理解为本贾尼在使用C语言的时候认为有缺陷&#xff0c;于是加了一些小语法进行改良&#xff0c;后来经过委员会的修改&#xff0c;C98问世…

C#手术麻醉系统源码 可对接HIS LIS PACS 医疗系统各类设备 医院手麻系统源码

C#手术麻醉系统源码 可对接HIS LIS PACS 医疗系统各类设备 手术麻醉信息管理系统主要还是为了手术室开发提供全面帮助的系统&#xff0c;其主要是由监护设备数据采集子系统和麻醉临床系统两个子部分组成。包括从手术申请到手术分配&#xff0c;再到术前访视、术中记录及术后…