​LeetCode解法汇总2707. 字符串中的额外字符

news/2024/4/14 20:49:14

 目录链接:

力扣编程题-解法汇总_分享+记录-CSDN博客

GitHub同步刷题项目:

https://github.com/September26/java-algorithms

原题链接:. - 力扣(LeetCode)


描述:

给你一个下标从 0 开始的字符串 s 和一个单词字典 dictionary 。你需要将 s 分割成若干个 互不重叠 的子字符串,每个子字符串都在 dictionary 中出现过。s 中可能会有一些 额外的字符 不在任何子字符串中。

请你采取最优策略分割 s ,使剩下的字符 最少 。

示例 1:

输入:s = "leetscode", dictionary = ["leet","code","leetcode"]
输出:1
解释:将 s 分成两个子字符串:下标从 0 到 3 的 "leet" 和下标从 5 到 8 的 "code" 。只有 1 个字符没有使用(下标为 4),所以我们返回 1 。

示例 2:

输入:s = "sayhelloworld", dictionary = ["hello","world"]
输出:3
解释:将 s 分成两个子字符串:下标从 3 到 7 的 "hello" 和下标从 8 到 12 的 "world" 。下标为 0 ,1 和 2 的字符没有使用,所以我们返回 3 。

提示:

  • 1 <= s.length <= 50
  • 1 <= dictionary.length <= 50
  • 1 <= dictionary[i].length <= 50
  • dictionary[i] 和 s 只包含小写英文字母。
  • dictionary 中的单词互不相同。

解题思路:

典型动态规划的题目。使用dp[i]代表到i位置时,使剩下的字符最少的数量。

那么dp[i]有两种来源,或者dp[i-1]+1,或者从某个位置跳跃而来。比如字符串abcd,字典["cd"]。

那么dp[3](位置d)要么dp[2]+1,要么dp[1](b的位置)直接拼接cd而来。

我们这样动态规划下去,最后dp[s.length()]就是我们想要的结果。

代码:

class Solution {public int minExtraChar(String s, String[] dictionary) {Map<String, List<String>> map = new HashMap<>();for (String word : dictionary) {String key = word.substring(word.length() - 1);List<String> list = map.computeIfAbsent(key, k -> new ArrayList<>());list.add(word);}int[] dp = new int[s.length() + 1];for (int i = 0; i < s.length(); i++) {dp[i + 1] = Math.min(dp[i], dp[i]) + 1;String key = s.substring(i, i + 1);List<String> list = map.get(key);if (list == null || list.size() == 0) {continue;}for (String str : list) {String compareStr = s.substring(Math.max(0, i + 1 - str.length()), i + 1);if (str.equals(compareStr)) {dp[i + 1] = Math.min(dp[i + 1], dp[i - str.length() + 1]);}}System.out.print(dp[i + 1]);}return dp[s.length()];}
}


http://www.ppmy.cn/news/1300874.html

相关文章

汽车中的ECU、VCU、MCU、HCU

一、ECU是汽车电脑&#xff0c;刷汽车电脑可以提高动力&#xff0c;也可以减低动力&#xff0c;看需求。 简单原理如下。 1.汽车发动机运转由汽车电脑&#xff08;即ECU&#xff09;控制。 2.ECU控制发动机的进气量&#xff0c;喷油量&#xff0c;点火时间等&#xff0c;从而…

【技术选型】Doris vs starRocks

比对结论 仅从当前能看到的数据中&#xff0c;相比于doris&#xff0c;starRocks在性能方面具备优势&#xff0c;且更新频率高&#xff08;降低维护成本&#xff09;。 目标诉求 并发性不能太低——相比于clickhouse不到100的QPS支持大表关联——降低数据清洗的压力&#xf…

MySQL篇—通过Clone插件进行本地克隆数据(第二篇,总共三篇)

在上一篇文章中&#xff0c;我们深入探讨了Clone技术的多种用途&#xff0c;以及使用它所需满足的前提条件。我们也详细分析了Clone存在的限制&#xff0c;并深入了解了其背后的备份原理。今天&#xff0c;我们将继续探索MySQL Clone Plugin的强大功能&#xff0c;Clone其实最重…

橘子学K8S03之容器的理解

前面我们知道了容器是通过对一个普通的linux进程进行隔离和限制实现的一种特殊视角下的进程表现。而隔离和限制的实现技术分别是"Namespace"和“Cgroups”,在这两种机制的控制下&#xff0c;我们需要知道容器的本质是一种特殊的进程。 我们现在有了这个认知之后&…

通义千问AI挑战赛赛后反思

个人理解&#xff1a; 初赛阶段主要聚焦在如何通过 SFT 提升基础模型的代码能力&#xff0c;需要选手基于最新开源的 Qwen 1.8 模型作为基础模型&#xff0c;上分的关键主要通过收集高质量的代码数据提升模型的在Python, JavaScript, Java, Go, C, Rust六种编程语言的代码生成…

openssl3.2 - 编译

文章目录 openssl3.2 - 编译概述OpenSSL源码下载编译目标如何编译前置环境 - perl前置环境 - VS前置环境 - NASM快速编译步骤编译 - Quick startInstall PerlInstall NASMUse Visual Studio Developer Command Prompt with administrative privilegesFrom the root of the Open…

傅里叶变换和逆变换

import cv2 import numpy as np import matplotlib.pyplot as plt import torch# 降低图像亮度image_path "eval15/gt/1.png" original_image cv2.imread(image_path)original_image_tensor torch.from_numpy(original_image.transpose(2, 0, 1)).float()x torch…

window中安装Apache http server(httpd-2.4.58-win64-VS17)

windows中安装Apache http server(httpd-2.4.58-win64-VS17) 1、下载windows版本的的httpd, https://httpd.apache.org/docs/current/platform/windows.html#down 这里选择的是Apache Lounge编译的版本 https://www.apachelounge.com/download/ 2、解压到指定目录&#xff0c;这…

Mybatis自动加解密

涉及隐私信息的字段需要加密存储数据库&#xff0c;返回给前端时又需要解密显示正确信息。故采用mybatis自动加解密的方案&#xff0c;该方案基于自定义注解拦截器进行实现。加密后的信息不支持模糊匹配&#xff08;可参考业界流行方案&#xff0c;基于业务需求做分词或采用其他…

docker容器内运行python多进程卡住

在启动多进程的文件头部执行如下代码即可&#xff1a; import multiprocessing as mptry:mp.set_start_method(spawn, forceTrue)print("spawned") except RuntimeError:pass 参考&#xff1a; multiprocessing - mp.set_start_method(spawn) triggered an error …

【AI视野·今日NLP 自然语言处理论文速览 第七十二期】Mon, 8 Jan 2024

AI视野今日CS.NLP 自然语言处理论文速览 Mon, 8 Jan 2024 Totally 17 papers &#x1f449;上期速览✈更多精彩请移步主页 Daily Computation and Language Papers DeepSeek LLM: Scaling Open-Source Language Models with Longtermism Authors DeepSeek AI Xiao Bi, Deli Ch…

Tomcat 的 work 目录缓存导致的JSP页面图片更新问题

一、问题分析 1. 修改后重新部署没有变化 笔者之前部署了一个后台管理项目&#xff0c;通过它来发布课程内容&#xff0c;其中有一个 JSP 课程页面&#xff0c;在该 JSP 页面里也引用了类文件 Constant.java 里的一个变量&#xff08;ALIYUN_OSS_PATH&#xff09;&#xff0c;…

【LeetCode】2619. 数组原型对象的最后一个元素

数组原型对象的最后一个元素 题目题解 题目 请你编写一段代码实现一个数组方法&#xff0c;使任何数组都可以调用 array.last() 方法&#xff0c;这个方法将返回数组最后一个元素。如果数组中没有元素&#xff0c;则返回 -1。 你可以假设数组是 JSON.parse 的输出结果。 示例 …

Shopify绑定Facebook收费吗?付款方式是什么?-站斧浏览器

Shopify绑定Facebook收费吗&#xff1f; 答案是&#xff1a;Shopify绑定Facebook并不收取额外费用。Shopify和Facebook之间的绑定是免费的&#xff0c;卖家可以充分利用这一功能来扩展他们的在线业务。通过将商店与Facebook Page相连接&#xff0c;卖家可以将产品目录同步到Fa…

C++OpenCV学习笔记(0):从开始到放弃

文章目录 前言环境配置Hello worldC 和C# 语法对比模板字符串list列表 总结 前言 作为一个计算机本科学生&#xff0c;我大学的时候深深的被指针和内存管理给折磨过。我深刻的理解内存泄漏的巨大问题。但是我最近学习Python的时候发现&#xff0c;Python是真的不好进行项目管理…

google关键词分析怎么做?

想分析关键词那自然是要使用工具&#xff0c;而分析一个关键词比较看重的有两点&#xff0c;搜索量以及竞争程度。 搜索量无非就是关键词在谷歌搜索引擎被搜索的次数&#xff0c;这个数量越大&#xff0c;就证明这个关键词被人搜的越多次&#xff0c;我们要做的词&#xff0c;肯…

【Unity】云的渲染

简述&#xff1a; 大佬总结的方法很多&#xff0c;不重复造轮子和搬运&#xff0c;所参考的链接&#xff0c;和测试的demo在Gitee里。 基于Mesh顶点偏移的云海效果&#xff08;Done&#xff09;基于面片和噪声的云效果&#xff08;Done&#xff09;基于模型的体积云&#xff…

在Windows服务器上部署项目【虚拟机版】

一. jdk的安装 1、直接双击jdk应用程序&#xff0c;然后下一步下一步即可。 2、安装完成后&#xff0c;在此电脑➡右键➡属性➡高级系统变量。 3、配置环境变量 新建JAVA_HOMEC:\Program Files\Java\jdk1.8.0_144 编辑pathpath%JAVA_HOME%\bin;%JAVA_HOME%\jre\bin; 4、测试&am…

【数据库原理】(23)实际应用中的查询优化方法

一.基于索引的优化 索引是数据库查询优化的关键工具之一。合理地使用索引可以显著提高查询速度&#xff0c;降低全表扫描的成本。以下是建立和使用索引的一些基本原则和最佳实践。 索引的建立与使用原则 数据量规模与查询频率: 值得建立索引的表通常具有较多的记录&#xff0…

tiktok_浅谈hook ios之发包x-ss-stub

frida-trace ios手机一部&#xff0c;需要越狱的电脑一台idacrackerXI 目标app&#xff1a; ipa 包&#xff0c;点击前往 密码&#xff1a;8urs 协议分析起始从抓包开始&#xff0c;个人习惯 一般安卓逆向可以直接搜关键词&#xff0c;但是ios 都在 Mach-O binary (reverse…
最新文章