Leetcode-1278.Palindrome Partitioning III [C++][Java]

目录

一、题目描述

二、解题思路

【C++】

【Java】


Leetcode-1278.Palindrome Partitioning IIIhttps://leetcode.com/problems/palindrome-partitioning-iii/description/1278. 分割回文串 III - 力扣(LeetCode)1278. 分割回文串 III - 给你一个由小写字母组成的字符串 s,和一个整数 k。请你按下面的要求分割字符串: * 首先,你可以将 s 中的部分字符修改为其他的小写英文字母。 * 接着,你需要把 s 分割成 k 个非空且不相交的子串,并且每个子串都是回文串。请返回以这种方式分割字符串所需修改的最少字符数。 示例 1:输入:s = "abc", k = 2输出:1解释:你可以把字符串分割成 "ab" 和 "c",并修改 "ab" 中的 1 个字符,将它变成回文串。示例 2:输入:s = "aabbc", k = 3输出:0解释:你可以把字符串分割成 "aa"、"bb" 和 "c",它们都是回文串。示例 3:输入:s = "leetcode", k = 8输出:0 提示: * 1 <= k <= s.length <= 100 * s 中只含有小写英文字母。https://leetcode.cn/problems/palindrome-partitioning-iii/

一、题目描述

You are given a string s containing lowercase letters and an integer k. You need to :

  • First, change some characters of s to other lowercase English letters.
  • Then divide s into k non-empty disjoint substrings such that each substring is a palindrome.

Return the minimal number of characters that you need to change to divide the string.

Example 1:

Input: s = "abc", k = 2
Output: 1
Explanation: You can split the string into "ab" and "c", and change 1 character in "ab" to make it palindrome.

Example 2:

Input: s = "aabbc", k = 3
Output: 0
Explanation: You can split the string into "aa", "bb" and "c", all of them are palindrome.

Example 3:

Input: s = "leetcode", k = 8
Output: 0

Constraints:

  • 1 <= k <= s.length <= 100.
  • s only contains lowercase English letters.

二、解题思路

  • 时间复杂度:O(n^2*k)

  • 空间复杂度:O(n^2+n*k)

【C++】

class Solution {
public:int palindromePartition(string s, int k) {vector<vector<int>> change(s.size(), vector<int>(s.size(), 0));for (int l = s.size() - 2; l >= 0; --l) {for (int r = l + 1; r < s.size(); ++r) {change[l][r] = change[l + 1][r - 1] + (s[l] == s[r] ? 0 : 1);}}vector<vector<int>> dp(k, vector<int>(s.size(), INT_MAX));dp[0] = move(change[0]);for (int i = 1; i < k; ++i) {for (int r = i; r <= s.size() - k + i; ++r) {for (int l = i; l <= r; ++l) {dp[i][r] = min(dp[i][r], dp[i - 1][l - 1] + change[l][r]);}}}return dp[k - 1][s.size() - 1];}
};

【Java】

class Solution {public int palindromePartition(String s, int k) {int[][] change = new int[s.length()][s.length()];for (int l = s.length() - 2; l >= 0; --l) {for (int r = l + 1; r < s.length(); ++r) {change[l][r] = change[l + 1][r - 1] + (s.charAt(l) == s.charAt(r) ? 0 : 1);}}int[][] dp = new int[k][s.length()];for (int i = 0; i < k; ++i) Arrays.fill(dp[i], Integer.MAX_VALUE);dp[0] = change[0];for (int i = 1; i < k; ++i) {for (int r = i; r <= s.length() - k + i; ++r) {for (int l = i; l <= r; ++l) {dp[i][r] = Math.min(dp[i][r], dp[i - 1][l - 1] + change[l][r]);}}}return dp[k - 1][s.length() - 1];}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/34878.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

deepseek GRPO算法保姆级讲解(数学原理+源码解析+案例实战)

文章目录 什么是GRPO群组形成(Group Formation):让大模型创建多种解决方案偏好学习(Preference Learning)&#xff1a;让大模型理解何为好的解答组内相对优势 优化(optimization): 让大模型从经验中学习(learning from experience)目标函数 GRPO算法的伪码表示GRPO算法的局限与…

【Linux我做主】基础命令完全指南上篇

Linux基础命令完全指南【上篇】 Linux基础命令完全指南github地址前言命令行操作的引入Linux文件系统树形结构的根文件系统绝对路径和相对路径适用场景Linux目录下的隐藏文件 基本指令目录和文件相关1. ls2. cd和pwdcdpwd 3. touch4. mkdir5. cp6. mv移动目录时覆盖写入的两种特…

自然语言秒转SQL—— 免费体验 OB Cloud Text2SQL 数据查询

在数据驱动决策的今天&#xff0c;企业急需从庞大业务数据中提炼信息&#xff0c;获取深度洞察。然而&#xff0c;面对海量数据&#xff0c;业务人员往往因缺乏SQL专业技能而难以快速查询和分析所需信息&#xff0c;频繁求助于BI部门不仅抬高了企业的沟通与时间成本&#xff0c…

鸿蒙next 多行文字加图片后缀实现方案

需求 实现类似iOS的YYLabel之类的在文字后面加上图片作为后缀的样式&#xff0c;多行时文字使用…省略超出部分&#xff0c;但必须保证图片的展现。 系统方案 在当前鸿蒙next系统提供的文字排版方法基本没有合适使用的接口&#xff0c;包括imagespan和RichEditor,根据AI的回…

C语言基础知识04---指针

目录 1、指针 1.1 指针概念 1.2 指针的大小 1.3 指针的定义 1.4 多级指针 1.5 指针的初始化 1.6 指针的使用 1.7 类型转换 1.8 大小端 1.9 地址偏移 1.10 指针常量&&常量指针 1.11 指针数组&&数组指针 1、指针 1.1 指针概念 指针保存地址&#xff…

spring boot 发送邮件验证码

一、前置需求 1、准备邮箱 2、登录授权码 qq邮箱在–>设置–>账号POP3/IMAP/SMTP/Exchange/CardDAV/CalDAV服务 开启服务 二、发送邮件 1、简单邮件 包含邮件标题、邮件正文 2、引入mail启动器 <dependency><groupId>org.springframework.boot</groupI…

Spring Cloud Config - 动态配置管理与高可用治理

引言&#xff1a;为什么需要配置中心&#xff1f; 在微服务架构中&#xff0c;配置管理面临分散化、多环境、动态更新三大挑战。传统基于application.yml等配置文件的硬编码方式&#xff0c;导致以下问题&#xff1a; • 环境差异&#xff1a;开发、测试、生产环境配置混杂&a…

[网络][tcp协议]:tcp报头

tcp(传输控制协议)是一种面向字节流的传输层协议,相较于udp协议,tcp能保证传输数据的可靠性与准确性,tcp也是目前最常见的传输层协议 本文主要介绍tcp报头各个字段的含义与用途 注:保留6位和6位标记位是目前最普遍的写法,在我查资料时,发现有一些拓展情况,会在后文细说 最简单的…

【sklearn 01】人工智能概述

一、人工智能&#xff0c;机器学习&#xff0c;深度学习 人工智能指由人类制造出的具有智能的机器。这是一个非常大的范围&#xff0c;长远目标是让机器实现人工智能&#xff0c;但目前我们仍处在非常初始的阶段&#xff0c;甚至不能称为智能 机器学习是指通过数据训练出能完成…

Excel ScriptLab学习笔记

注意 The Excel JavaScript API 没有“Cell”对象或类。 相反&#xff0c;Excel JavaScript API 将所有 Excel 单元格定义为 Range 对象。 Excel UI 中的单个单元格转换为 Excel JavaScript API 中包含一个单元格的 Range 对象。 单个 Range 对象也可以包含多个连续的单元格。…

【数据结构】线性表简介

0.本篇问题 线性表&#xff0c;顺序表&#xff0c;链表什么关系&#xff1f;它们是逻辑结构还是存储结构&#xff1f;线性表的基本操作有哪些&#xff1f; 线性表是具有相同数据元素的有限序列。 表中元素有先后次序&#xff0c;每个元素占有相同大小的存储空间。 一、线性…

设计模式(行为型)-备忘录模式

目录 定义 类图 角色 角色详解 &#xff08;一&#xff09;发起人角色&#xff08;Originator&#xff09;​ &#xff08;二&#xff09;备忘录角色&#xff08;Memento&#xff09;​ &#xff08;三&#xff09;备忘录管理员角色&#xff08;Caretaker&#xff09;​…

Navicat如何查看密码

近期遇到需要将大部分已存储的navicat数据库转发给其他人&#xff0c;于是乎进行导出文件 奈何对方不用navicat&#xff0c;无法进行文件的导入从而导入链接 搜罗navicat的密码查看&#xff0c;大部分都为php代码解析 以下转载GitHub上看到的一个python代码解析的脚本 这里是对…

Matlab 四分之一车体车辆半主动悬架鲁棒控制

1、内容简介 略 Matlab 173-四分之一车体车辆半主动悬架鲁棒控制 可以交流、咨询、答疑 2、内容说明 略 3、仿真分析 略 4、参考论文 略

Python学习第十九天

Django-分页 后端分页 Django提供了Paginator类来实现后端分页。Paginator类可以将一个查询集&#xff08;QuerySet&#xff09;分成多个页面&#xff0c;每个页面包含指定数量的对象。 from django.shortcuts import render, redirect, get_object_or_404 from .models impo…

【大模型】Transformer、GPT1、GPT2、GPT3、BERT 的论文解析

前言 在自然语言处理&#xff08;NLP&#xff09;和深度学习的快速发展中&#xff0c;Transformer模型和 GPT系列模型扮演了至关重要的角色。本篇博客旨在对这些开创性的论文进行介绍&#xff0c;涵盖它们的提出时间、网络结构等关键信息&#xff0c;能够快速的理解这些模型的设…

【DeepSeek应用】本地部署deepseek模型后,如何在vscode中调用该模型进行代码撰写,检视和优化?

若已成功在本地部署了 DeepSeek 模型(例如通过 vscode-llm、ollama 或私有 API 服务),在 VS Code 中调用本地模型进行代码撰写、检视和优化的完整流程如下: 1. 准备工作:确认本地模型服务状态 模型服务类型: 若使用 HTTP API 服务(如 FastAPI/Flask 封装),假设服务地址…

【C语言】函数和数组实践与应用:开发简单的扫雷游戏

【C语言】函数和数组实践与应用&#xff1a;开发简单的扫雷游戏 1.扫雷游戏分析和设计1.1扫雷游戏的功能说明&#xff08;游戏规则&#xff09;1.2游戏的分析与设计1.2.1游戏的分析1.2.2 文件结构设计 2. 代码实现2.1 game.h文件2.2 game.c文件2.3 test.c文件 3. 游戏运行效果4…

需求分析、定义、验证、变更、跟踪(高软47)

系列文章目录 需求分析、定义、验证、变更、跟踪 文章目录 系列文章目录前言一、需求分析二、需求定义三、需求验证四、需求变更五、需求跟踪六、真题总结 前言 本节讲明需求分析、定义、验证、变更、跟踪相关知识。 一、需求分析 二、需求定义 三、需求验证 四、需求变更 五、…

【拒绝算法PUA】LeetCode 2270. 分割数组的方案数

系列文章目录 【拒绝算法PUA】0x00-位运算 【拒绝算法PUA】0x01- 区间比较技巧 【拒绝算法PUA】0x02- 区间合并技巧 【拒绝算法PUA】0x03 - LeetCode 排序类型刷题 【拒绝算法PUA】LeetCode每日一题系列刷题汇总-2025年持续刷新中 C刷题技巧总结&#xff1a; [温习C/C]0x04 刷…