LeetCode 2707. 字符串中的额外字符

2024-01-10 05:52

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

一、题目

1、题目描述

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

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

2、接口描述

class Solution {
public:int minExtraChar(string s, vector<string>& dictionary) {}
};

3、原题链接

2707. 字符串中的额外字符


二、解题报告

1、思路分析

和上周周赛题目类似,也是分割字符串,我们可以用动态规划将问题划分为子问题

定义状态dp[i]为前i个字符最优划分后的最少额外字符,那么有转移方程:

dp[i] = dp[ i -1],将第i个字符作为额外字符

dp[i] = min(dp[i] , dp[j - 1]),其中第j个字符到第i个字符在字典中

最终返回dp[n]即可

进行状态转移,如果暴力计算子串是否在字典中,显然复杂度过高

如果将字典中字符串存入哈希表,那么每次状态转移为n * 2,因为我们要从(i , i)计算到(1 , i)

这里就涉及到查询字符串优化的常用策略,将目标字符串倒序存入字典树,然后倒序查询可以满足一次遍历完成查询,关于字典树见:Trie树/字典树的原理及实现[C/C++]-CSDN博客

2、复杂度

时间复杂度:O(n^2 + ml) 空间复杂度:O(m l * 26)

3、代码详解

class Solution
{
public:struct Node{bool isword = false;unordered_map<char, Node *> child;} root;void insert(string &s){Node *cur = &root;for (int i = s.size() - 1; i >= 0; i--){if (!cur->child.count(s[i]))cur->child[s[i]] = new Node;cur = cur->child[s[i]];}cur->isword = true;}int minExtraChar(string s, vector<string> &dictionary){root.child.clear();for (auto &x : dictionary)insert(x);int n = s.size();vector<int> dp(n + 1, INT_MAX);dp[0] = 0;for (int i = 1; i <= n; i++){dp[i] = dp[i - 1] + 1;Node *cur = &root;for (int j = i; j >= 1; j--){if (!cur->child.count(s[j - 1]))break;cur = cur->child[s[j - 1]];if (cur->isword)dp[i] = min(dp[i], dp[j - 1]);}}return dp[n];}
};

这篇关于LeetCode 2707. 字符串中的额外字符的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

golang float和科学计数法转字符串的实现方式

《golangfloat和科学计数法转字符串的实现方式》:本文主要介绍golangfloat和科学计数法转字符串的实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望... 目录golang float和科学计数法转字符串需要对float转字符串做处理总结golang float

Python如何判断字符串中是否包含特殊字符并替换

《Python如何判断字符串中是否包含特殊字符并替换》这篇文章主要为大家详细介绍了如何使用Python实现判断字符串中是否包含特殊字符并使用空字符串替换掉,文中的示例代码讲解详细,感兴趣的小伙伴可以了... 目录python判断字符串中是否包含特殊字符方法一:使用正则表达式方法二:手动检查特定字符Pytho

MySQL 字符串截取函数及用法详解

《MySQL字符串截取函数及用法详解》在MySQL中,字符串截取是常见的操作,主要用于从字符串中提取特定部分,MySQL提供了多种函数来实现这一功能,包括LEFT()、RIGHT()、SUBST... 目录mysql 字符串截取函数详解RIGHT(str, length):从右侧截取指定长度的字符SUBST

Python将字符串转换为小写字母的几种常用方法

《Python将字符串转换为小写字母的几种常用方法》:本文主要介绍Python中将字符串大写字母转小写的四种方法:lower()方法简洁高效,手动ASCII转换灵活可控,str.translate... 目录一、使用内置方法 lower()(最简单)二、手动遍历 + ASCII 码转换三、使用 str.tr

Java如何用乘号来重复字符串的功能

《Java如何用乘号来重复字符串的功能》:本文主要介绍Java使用乘号来重复字符串的功能,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Java乘号来重复字符串的功能1、利用循环2、使用StringBuilder3、采用 Java 11 引入的String.rep

idea报错java: 非法字符: ‘\ufeff‘的解决步骤以及说明

《idea报错java:非法字符:‘ufeff‘的解决步骤以及说明》:本文主要介绍idea报错java:非法字符:ufeff的解决步骤以及说明,文章详细解释了为什么在Java中会出现uf... 目录BOM是什么?1. BOM的作用2. 为什么会出现 \ufeff 错误?3. 如何解决 \ufeff 问题?最

使用Java编写一个字符脱敏工具类

《使用Java编写一个字符脱敏工具类》这篇文章主要为大家详细介绍了如何使用Java编写一个字符脱敏工具类,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录1、字符脱敏工具类2、测试工具类3、测试结果1、字符脱敏工具类import lombok.extern.slf4j.Slf4j

Java实现按字节长度截取字符串

《Java实现按字节长度截取字符串》在Java中,由于字符串可能包含多字节字符,直接按字节长度截取可能会导致乱码或截取不准确的问题,下面我们就来看看几种按字节长度截取字符串的方法吧... 目录方法一:使用String的getBytes方法方法二:指定字符编码处理方法三:更精确的字符编码处理使用示例注意事项方

解决IDEA报错:编码GBK的不可映射字符问题

《解决IDEA报错:编码GBK的不可映射字符问题》:本文主要介绍解决IDEA报错:编码GBK的不可映射字符问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录IDEA报错:编码GBK的不可映射字符终端软件问题描述原因分析解决方案方法1:将命令改为方法2:右下jav

Java中的StringBuilder之如何高效构建字符串

《Java中的StringBuilder之如何高效构建字符串》本文将深入浅出地介绍StringBuilder的使用方法、性能优势以及相关字符串处理技术,结合代码示例帮助读者更好地理解和应用,希望对大家... 目录关键点什么是 StringBuilder?为什么需要 StringBuilder?如何使用 St