(动态规划) 132. 分割回文串 II ——【Leetcode每日一题】

news/2024/4/15 14:54:01

❓ 132. 分割回文串 II

难度:困难

给你一个字符串 s,请你将 s 分割成一些子串,使每个子串都是回文。

返回符合要求的 最少分割次数

示例 1:

输入:s = “aab”
输出:1
解释:只需一次分割就可将 s 分割成 [“aa”,“b”] 这样两个回文子串。

示例 2:

输入:s = “a”
输出:0

示例 3:

输入:s = “ab”
输出:1

提示

  • 1 < = s . l e n g t h < = 2000 1 <= s.length <= 2000 1<=s.length<=2000
  • s 仅由小写英文字母组成

💡思路:动态规划

  • 先使用中心扩展法,计算以每个字符为中心的最长回文串,注意
    • 既可以 以单个字符为中心,此时的回文串长度为奇数个;
    • 也可以 以两个相同的字符为中心,此时的回文串为偶数个;
  • 在计算每个最长回文串的长度后,得到每个回文串的起始位置,并不断更新以该位置为起点的最长回文串的长度;

🍁代码:(C++、Java)

C++


Java


🚀 运行结果:

🕔 复杂度分析:

  • 时间复杂度 O ( n ) O(n) O(n),其中 n 为数组的长度。
  • 空间复杂度 O ( n ) O(n) O(n),其中 n 为数组的长度。

题目来源:力扣。

放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我LeetCode主页 / CSDN—力扣专栏,每日更新!

注: 如有不足,欢迎指正!


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

相关文章

Mac大小写切换需长按caps lock键解决办法

偏好设置—键盘—输入法—长按以启用全大写键入&#xff08;去掉前面的对号&#xff0c;注意&#xff1a;这一行字很小&#xff09;。

从键盘输入一个小写英文字母,将其转换为大写英文字母

#include <stdio.h> //编程从键盘输入一个小写英文字母&#xff0c;将其转换为大写英文字母&#xff0c;将转换后的大写英文字母及其十进制的ASCII码值显示在屏幕上。 int main(void) {printf("请输入一个小写字母&#xff1a;\n");char a,b;scanf("%c&qu…

小写字母转化为大写字母

【深基2.例6】字母转换 题目描述 输入一个小写字母&#xff0c;输出其对应的大写字母。例如输入 q时&#xff0c;会输出 Q。 输入格式 无 输出格式 无 输入输出样例 输入 #1 q 输出 #1 Q import java.util.Scanner;pub…

大写字母转换为小写

几行小代码简单的进行一下转换。这里的getchar&#xff08;&#xff09;和putchar&#xff08;&#xff09;起到的作用是输入输出&#xff0c;这个做为知识点要记住&#xff0c;EOF的全称为end of file 是文件结束标志&#xff0c;通常放在文件的末尾&#xff0c;这里做为循环判…

将小写字母转换为大写

将小写字母转换为大写 【问题描述】输入一个长度小于80的字符串&#xff0c;将小写字母转换为大写&#xff0c;如果输入串没有小写字母&#xff0c;则输出提示信息。要求在主函数中输入字符串&#xff0c;并输出结果&#xff0c;在被调函数中完成将小写字母转换为大写。 【输…

将大写字母转换为小写字母

欢迎加qq群&#xff1a;453398542 学习讨论&#xff0c;会定期分享资料课程&#xff0c;解答问题。 将大写字母转换为小写字母 #include<stdio.h> int main() { char a; printf("输入一个字母&#xff1a;"); scanf("%c",&a); aa>A&&…

小写数字转换成大写数字

#include<stdio.h> void main() {double x,y; char *ch[]={"零","壹","贰","叁","肆","伍","陆","柒","捌","玖"}; char *ch1[]={"拾","佰",…

从键盘输入一个大写字母,转换成小写字母

#include <stdio.h> int main() { char n; printf(“请输入一个大写字母:”); scanf("%c",&n); nn32; putchar(n); putchar(’\n’); return 0; }

大写字母转换为小写字母

编程从键盘输入一个大写英文字母&#xff0c;将其转换为小写英文字母&#xff0c;将转换后的小写英文字母及其十进制的ASCII码值显示到屏幕上。如果输入的不是大写英文字母&#xff0c;则输出Input Data error!。 输入格式: 从键盘输入一个大写的英文字母&#xff0c;以回车结…

Mac OS X 键盘字母键和数字键的切换

VMware10中运行的Mac OS X &#xff1a; 键盘不知道按到了什么&#xff0c;切换到数字小键盘了&#xff08;u键变成4&#xff0c;i变成5&#xff0c;o变成6等&#xff09;&#xff0c;怎么切换数字键和字母键&#xff1f; 最后发现是CapsLk键&#xff0c;按了一下大小写锁定键…

键盘输入字符串 数字转换为 * 英文字母大写转小写 小写转大写

public static void main(String[] args) {Scanner s new Scanner(System.in);System.out.println("请输入您想输入的字符串&#xff1a;");String str s.next();StringBuffer sb new StringBuffer();int i;for (i 0; i < str.length() - 1; i) {char ch;if (…

完美解决苹果电脑mac终端无法输入大写T的问题

[本文出自天外归云的博客园] 最近突然发现我的苹果电脑mac终端无法输入大写字母T&#xff0c;今天终于在同事的帮助下解决了&#xff01;之前在网上查解决方法&#xff0c;感觉步骤描述欠佳&#xff01;今天记录一下这个踩坑经验&#xff1a; 完美解决&#xff01; 首先打开终端…

哪里有适合Mac苹果电脑系统的音频格式转换软件

在我们的音频制作过程中&#xff0c;难免会碰到音频格式转换问题&#xff0c;例如m4a转mp3&#xff0c;wav转aac等多格式转换问题&#xff0c;那么作为Mac苹果电脑系统用户&#xff0c;在哪里去找一款合适的音频格式转换软件呢&#xff1f;   音频剪辑是一款出色的操作方便的…

iOS 大写字母与小写字母之间的转换

实现中文名取到其首字母的代码 - (NSMutableString *)firstCharactor:(NSString *)aString {NSMutableString *strSum [[NSMutableString alloc]init];for (int i 0 ; i < aString.length ; i) {//转成了可变字符串NSMutableString *str [NSMutableString stringWithStri…

大小写转换(大小写转换键是哪个键)

C语言编程 大小写转换 #include "stdio.h" int main( ) { int i0; char arr[100]; scanf("%s",arr); while(\0!arr[i]) { if(arr[i]>a&&arr[i]<z) arr[i]-32; else if(arr[i]>A&&arr[i]<Z) arr[i]肌耽冠甘攉仿圭湿氦溅32; i; …

苹果电脑怎样禁用首字母自动大写?

苹果电脑在一些文字编辑软件中输入英文的时候&#xff0c;Mac会自动识别进行首字母大写&#xff0c;但是如果是写一些脚本之类的话就会非常麻烦&#xff0c;所以要禁用这个功能。那我们该如何禁用首字母自动大写呢&#xff1f;需要的朋友快和小编一起来看看具体的操作方法吧&am…

Mac:使用大写锁定键切换输入法

Mac&#xff1a;使用大写锁定键切换输入法 动机 大写锁定键是我的键盘上用的最少的键之一。说是之一&#xff0c;一是因为我的键盘上还有一个关机键使用频率和它有的一拼&#xff0c;二是由于其地理位置优越经常会被误按。 实际上&#xff0c;在Chromebook上&#xff0c;大写锁…

macbook pro 怎么打大写字母

原文地址::https://zhidao.baidu.com/question/198291859.html 相关文章 1、[求助] Mac打不了大写英文字母----https://bbs.feng.com/read-htm-tid-10841270.html // 本人备注 1> 长按一会caps键就可以大写了

读者与写者问题

本篇文章我们使用C探讨一下读者与写者问题. 1. 读者与写者问题引入 读写操作是计算机中对存储区最常见的两种操作. 我们之前探讨了生产者与消费者问题, 知道了如何开启多个线程, 现在就可以直接写出读者与写者问题的最基本的代码了, 仍从最简单的情况开始--两个读者, 代码如下…

网络编程-day3

UDP服务器&#xff1a; UDP客户端&#xff1a;
最新文章