当前位置: 首页 > article >正文

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.kler.cn/a/588607.html

相关文章:

  • 使用 Flask 进行简单服务器改造的详细步骤和代码
  • 在 React 中使用 Web Components 的实践操作
  • Blender-MCP服务源码1-项目解读
  • Linux find 命令完全指南
  • 接口测试中常见的bug有哪些?
  • 使用elementplus的table表格遇到的问题
  • ubuntu ollama+dify实践
  • 关于修改 Ollama 及其模型默认路径、迁移已安装的 Ollama 程序和模型以及重启 Ollama 的操作指南
  • 计算机视觉——深入理解卷积神经网络与使用卷积神经网络创建图像分类算法
  • 在线 SQL 转 Flask-SQLAlchemy
  • 高版本node(17+)环境下VUE2项目启动报错
  • Android 7 及以上夜神模拟器,Fiddler 抓 https 包
  • DDS:保障物联网系统的稳定运行和高效协作
  • 提升 React 应用性能:使用 React Profiler 进行性能调优
  • Assembly语言的自然语言处理
  • Spring Boot项目中成功集成了JWT
  • C++学习内存管理
  • 【NLP 38、实践 ⑩ NER 命名实体识别任务 Bert 实现】
  • STM32 - 在机器人领域,LL库相比HAL优势明显
  • RAG数据嵌入和重排序:如何选择合适的模型