算法每日一题:字符串中的额外字符 | 动归 | 哈希 | 字符串

2024-01-14 06:12

本文主要是介绍算法每日一题:字符串中的额外字符 | 动归 | 哈希 | 字符串,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

大家好,我是星恒
呜呜呜,又是拖更的几天,这几天由于考试 + 放假,一直是只做没发的状态,今天就将这几天的每日一题都补回来啦!

今天给大家带来的又是神奇的动归

题目:leetcode 2707
给你一个下标从 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 中的单词互不相同。

分析:
维护一个大小为s.length()的dp数组,遍历s中的每个字母(i),然后再从当前字母开始往前遍历(j),看i与j之间的字母构成的字符串是否在dictionary中,也就是能否构成一个单词,如果可以,我们比较现在这种分割造成的剩下字符最少,还是之前分割剩余数 + 1的剩下字符最少

题解:

class Solution {public int minExtraChar(String s, String[] dictionary) {int n = s.length();int[] d = new int[n + 1];Arrays.fill(d, Integer.MAX_VALUE);Map<String, Integer> map = new HashMap<String, Integer>();for (String str : dictionary) {map.put(str, map.getOrDefault(str, 0) + 1);}d[0] = 0;for (int i = 1; i <= n; i++) {d[i] = d[i - 1] + 1;for (int j = i - 1; j >= 0; j--) {if (map.containsKey(s.substring(j, i))) {d[i] = Math.min(d[i], d[j]);}}}return d[n];}
}

如果大家有什么思考和问题,可以在评论区讨论,也可以私信我,很乐意为大家效劳。
好啦,今天的每日一题到这里就结束了,如果大家觉得有用,可以可以给我一个小小的赞呢,我们下期再见!

这篇关于算法每日一题:字符串中的额外字符 | 动归 | 哈希 | 字符串的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Java中字符串转时间与时间转字符串的操作详解

《Java中字符串转时间与时间转字符串的操作详解》Java的java.time包提供了强大的日期和时间处理功能,通过DateTimeFormatter可以轻松地在日期时间对象和字符串之间进行转换,下面... 目录一、字符串转时间(一)使用预定义格式(二)自定义格式二、时间转字符串(一)使用预定义格式(二)自

Java字符串操作技巧之语法、示例与应用场景分析

《Java字符串操作技巧之语法、示例与应用场景分析》在Java算法题和日常开发中,字符串处理是必备的核心技能,本文全面梳理Java中字符串的常用操作语法,结合代码示例、应用场景和避坑指南,可快速掌握字... 目录引言1. 基础操作1.1 创建字符串1.2 获取长度1.3 访问字符2. 字符串处理2.1 子字

一文详解如何在Python中从字符串中提取部分内容

《一文详解如何在Python中从字符串中提取部分内容》:本文主要介绍如何在Python中从字符串中提取部分内容的相关资料,包括使用正则表达式、Pyparsing库、AST(抽象语法树)、字符串操作... 目录前言解决方案方法一:使用正则表达式方法二:使用 Pyparsing方法三:使用 AST方法四:使用字

Java字符串处理全解析(String、StringBuilder与StringBuffer)

《Java字符串处理全解析(String、StringBuilder与StringBuffer)》:本文主要介绍Java字符串处理全解析(String、StringBuilder与StringBu... 目录Java字符串处理全解析:String、StringBuilder与StringBuffer一、St

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

MySQL更新某个字段拼接固定字符串的实现

《MySQL更新某个字段拼接固定字符串的实现》在MySQL中,我们经常需要对数据库中的某个字段进行更新操作,本文就来介绍一下MySQL更新某个字段拼接固定字符串的实现,感兴趣的可以了解一下... 目录1. 查看字段当前值2. 更新字段拼接固定字符串3. 验证更新结果mysql更新某个字段拼接固定字符串 -

Java String字符串的常用使用方法

《JavaString字符串的常用使用方法》String是JDK提供的一个类,是引用类型,并不是基本的数据类型,String用于字符串操作,在之前学习c语言的时候,对于一些字符串,会初始化字符数组表... 目录一、什么是String二、如何定义一个String1. 用双引号定义2. 通过构造函数定义三、St

golang获取当前时间、时间戳和时间字符串及它们之间的相互转换方法

《golang获取当前时间、时间戳和时间字符串及它们之间的相互转换方法》:本文主要介绍golang获取当前时间、时间戳和时间字符串及它们之间的相互转换,本文通过实例代码给大家介绍的非常详细,感兴趣... 目录1、获取当前时间2、获取当前时间戳3、获取当前时间的字符串格式4、它们之间的相互转化上篇文章给大家介

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》:本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘