力扣刷题-如何把时间超限代码改回正道?-用动态规划题力扣139 单词拆分来分享-c++实现

本文主要是介绍力扣刷题-如何把时间超限代码改回正道?-用动态规划题力扣139 单词拆分来分享-c++实现,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

在这里插入图片描述
在这里插入图片描述

题目链接:单词拆分链接

  • 最开始的代码,把三个小样例都过了

  • 详细注释版代码如下:

class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {unordered_set<string> mySet;mySet.insert(s);  // 初始化集合,将原始字符串 s 插入集合中,用于后续处理int len = wordDict.size(); // 获取字典中单词的总个数while (!mySet.empty()) {  // 当集合不为空时,继续处理// 每次从集合中取出第一个字符串auto it = mySet.begin();string temp = *it;  // 获取当前字符串char u = temp[0];  // 获取当前字符串的第一个字符int ll = temp.size();  // 获取当前字符串的长度// 遍历字典中的每一个单词for (string& st : wordDict) {int l = st.size();  // 获取字典中当前单词的长度if (ll < l) continue;  // 如果当前字符串长度小于字典单词长度,跳过// 如果当前字符串的第一个字符与字典单词的第一个字符相同if (u == st[0]) {// 检查当前字符串的前缀是否与字典单词相等if (temp.substr(0, l) == st) {// 如果当前字符串完全匹配字典单词,且没有剩余部分,直接返回 trueif (ll == l)return true;// 如果当前字符串匹配了字典单词的前缀,但有剩余部分,将剩余部分加入集合继续处理mySet.insert(temp.substr(l));}}}// 使用迭代器直接移除集合中的当前字符串,这样做可以提高效率mySet.erase(it);}return false;  // 如果集合处理完毕仍未找到匹配,返回 false}
};

无奈提交的时候时间超限:
在这里插入图片描述

后来我进行如下几种优化时间的办法:
  • 1.erase的时候直接写迭代器
auto it = mySet.begin();
string temp = *it;
mySet.erase(it);  // 通过迭代器删除

如果mySet.erase(temp);

这是通过值 temp 来移除元素。该方式需要 unordered_set 再次查找 temp,以确定要移除的元素的位置,因此会稍微低效一些,因为它相当于进行了两次查找:一次是 mySet.find(temp),然后再进行删除。

  • 2.substr(0, i) 操作尽量减少,因为时间复杂度是O(n) 还是比较大的,我之前都是通过这个函数取子串,然后和dict里的内容匹配,所以用的比较多,于是有了下一点改进

  • 3.字典使用 unordered_set 存储

    • 通过将 wordDict 存储在 unordered_set 中,查找字符串是否在字典中的时间复杂度从 O(n) 降低到 O(1)。
    • 直接通过 unordered_set<string> dict(wordDict.begin(), wordDict.end()); 进行数据结构转换,实现查找的时间复杂度降低,避免遍历dict内容
    • 总结:需要大范围查找的vector,就转unordered_set!不仅省时间,还去重!
  • 4.还有就是如果dict中有很多很小的子串,比如说a这种,在识别到了以后就乘胜追击,看是不是还能继续匹配:

    while (temp.substr(i, le) == prefix)i += le;
    
  • 其他题目的经验:能不用bool就不用bool,直接用int(时间效率会高很多),如果要返回bool的话,会自动转型成bool的

于是终于ac,时间内存都不错:

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

写好注释的代码如下:

class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {unordered_set<string> mySet;mySet.insert(s);  // 将初始字符串 s 插入到集合 mySet 中,用于后续处理int len = wordDict.size(); // 获取字典中单词的总数unordered_set<string> dict(wordDict.begin(), wordDict.end());  // 将字典中的单词存储到一个无序集合 dict 中,以加速查找操作// 当集合 mySet 不为空时,继续处理while (!mySet.empty()) {// 从集合中取出第一个字符串auto it = mySet.begin();string temp = *it;  // 获取当前字符串int ll = temp.size();  // 获取当前字符串的长度// 遍历字符串的每一个前缀for (int i = 1; i <= ll; ++i) {string prefix = temp.substr(0, i); // 获取当前长度为 i 的前缀// 如果前缀存在于字典中if (dict.find(prefix) != dict.end()) {int le = i;  // 记录前缀的长度mySet.insert(temp.substr(i)); // 将剩余部分插入集合中// 跳过连续重复的前缀部分while (temp.substr(i, le) == prefix)i += le;// 如果 i 已经遍历完字符串的全部长度,说明匹配成功if (i == ll) {return true; // 完全匹配,返回 true}// 将剩余部分插入集合中,以便后续处理mySet.insert(temp.substr(i));}}// 使用迭代器删除已处理的字符串,避免重复处理,提升效率mySet.erase(it);}// 如果所有可能性都处理完仍未找到可行的拆分,返回 falsereturn false;}
};
  • 之后我看了官方题解,和我是 不同的思路,写上注释供大家学习:
class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {// 将字典中的所有单词插入到无序集合中,以便于高效查找auto wordDictSet = unordered_set<string>();for (auto word : wordDict) {wordDictSet.insert(word); // 插入每一个单词到无序集合中}// 动态规划数组 dp,dp[i] 表示 s 的前 i 个字符能否被拆分成字典中的单词auto dp = vector<bool>(s.size() + 1);dp[0] = true; // 空字符串是可以被拆分的,这是递推的起点// 开始动态规划,逐个增加字符串长度for (int i = 1; i <= s.size(); ++i) {for (int j = 0; j < i; ++j) {// 检查从 j 到 i 的子字符串是否在字典中if (dp[j] && wordDictSet.find(s.substr(j, i - j)) != wordDictSet.end()) {dp[i] = true; // 如果找到匹配,标记 dp[i] 为 truebreak; // 不需要继续检查其他 j,直接跳出内层循环}}}// 返回 dp[s.size()],表示整个字符串 s 能否被拆分成字典中的单词return dp[s.size()];}
};

这篇关于力扣刷题-如何把时间超限代码改回正道?-用动态规划题力扣139 单词拆分来分享-c++实现的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1095167

相关文章

SpringBoot3实现Gzip压缩优化的技术指南

《SpringBoot3实现Gzip压缩优化的技术指南》随着Web应用的用户量和数据量增加,网络带宽和页面加载速度逐渐成为瓶颈,为了减少数据传输量,提高用户体验,我们可以使用Gzip压缩HTTP响应,... 目录1、简述2、配置2.1 添加依赖2.2 配置 Gzip 压缩3、服务端应用4、前端应用4.1 N

SpringBoot实现数据库读写分离的3种方法小结

《SpringBoot实现数据库读写分离的3种方法小结》为了提高系统的读写性能和可用性,读写分离是一种经典的数据库架构模式,在SpringBoot应用中,有多种方式可以实现数据库读写分离,本文将介绍三... 目录一、数据库读写分离概述二、方案一:基于AbstractRoutingDataSource实现动态

Python FastAPI+Celery+RabbitMQ实现分布式图片水印处理系统

《PythonFastAPI+Celery+RabbitMQ实现分布式图片水印处理系统》这篇文章主要为大家详细介绍了PythonFastAPI如何结合Celery以及RabbitMQ实现简单的分布式... 实现思路FastAPI 服务器Celery 任务队列RabbitMQ 作为消息代理定时任务处理完整

springboot循环依赖问题案例代码及解决办法

《springboot循环依赖问题案例代码及解决办法》在SpringBoot中,如果两个或多个Bean之间存在循环依赖(即BeanA依赖BeanB,而BeanB又依赖BeanA),会导致Spring的... 目录1. 什么是循环依赖?2. 循环依赖的场景案例3. 解决循环依赖的常见方法方法 1:使用 @La

Java枚举类实现Key-Value映射的多种实现方式

《Java枚举类实现Key-Value映射的多种实现方式》在Java开发中,枚举(Enum)是一种特殊的类,本文将详细介绍Java枚举类实现key-value映射的多种方式,有需要的小伙伴可以根据需要... 目录前言一、基础实现方式1.1 为枚举添加属性和构造方法二、http://www.cppcns.co

使用Python实现快速搭建本地HTTP服务器

《使用Python实现快速搭建本地HTTP服务器》:本文主要介绍如何使用Python快速搭建本地HTTP服务器,轻松实现一键HTTP文件共享,同时结合二维码技术,让访问更简单,感兴趣的小伙伴可以了... 目录1. 概述2. 快速搭建 HTTP 文件共享服务2.1 核心思路2.2 代码实现2.3 代码解读3.

使用C#代码在PDF文档中添加、删除和替换图片

《使用C#代码在PDF文档中添加、删除和替换图片》在当今数字化文档处理场景中,动态操作PDF文档中的图像已成为企业级应用开发的核心需求之一,本文将介绍如何在.NET平台使用C#代码在PDF文档中添加、... 目录引言用C#添加图片到PDF文档用C#删除PDF文档中的图片用C#替换PDF文档中的图片引言在当

C#使用SQLite进行大数据量高效处理的代码示例

《C#使用SQLite进行大数据量高效处理的代码示例》在软件开发中,高效处理大数据量是一个常见且具有挑战性的任务,SQLite因其零配置、嵌入式、跨平台的特性,成为许多开发者的首选数据库,本文将深入探... 目录前言准备工作数据实体核心技术批量插入:从乌龟到猎豹的蜕变分页查询:加载百万数据异步处理:拒绝界面

MySQL双主搭建+keepalived高可用的实现

《MySQL双主搭建+keepalived高可用的实现》本文主要介绍了MySQL双主搭建+keepalived高可用的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,... 目录一、测试环境准备二、主从搭建1.创建复制用户2.创建复制关系3.开启复制,确认复制是否成功4.同

Java实现文件图片的预览和下载功能

《Java实现文件图片的预览和下载功能》这篇文章主要为大家详细介绍了如何使用Java实现文件图片的预览和下载功能,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... Java实现文件(图片)的预览和下载 @ApiOperation("访问文件") @GetMapping("