萤火小屋

优律的知识库

  • 首页
  • 归档
  • 分类
  • 标签
  • 留言
  • 关于

  • 搜索
消息队列 RabbitMQ Redis 双指针 力扣 动态代理 Git YAML SpringBoot SpringMVC 回溯算法 分治算法 归并排序 快排 手撕 事务 MySQL索引 MySQL 小技巧 Spring Framework Spring 动态规划 Linux Android 贪心算法 操作系统 进程调度模拟 IPv6 数据库 计算机组成原理 计算机基础 栈 Java 静态路由 路由器 交换机 数字通信 网络工程 计算机网络 Web http 大学学习技巧 程序设计 算法

力扣1312题-让字符串成为回文串的最少插入次数-动态规划题解

发表于 2021-04-19 | 分类于 力扣刷题 | 0 | 阅读次数 276

题目描述

给你一个字符串 s ,每一次操作你都可以在字符串的任意位置插入任意字符。
请你返回让 s 成为回文串的 最少操作次数 。
“回文串”是正读和反读都相同的字符串。

样例

  1. 示例 1:
    输入:s = "zzazz"
    输出:0
    解释:字符串 "zzazz" 已经是回文串了,所以不需要做任何插入操作。

  2. 示例 2:
    输入:s = "mbadm"
    输出:2
    解释:字符串可变为 "mbdadbm" 或者 "mdbabdm" 。

  3. 示例 3:
    输入:s = "leetcode"
    输出:5
    解释:插入 5 个字符后字符串变为 "leetcodocteel" 。

  4. 示例 4:
    输入:s = "g"
    输出:0

  5. 示例 5:
    输入:s = "no"
    输出:1
     

  • 提示:
    1 <= s.length <= 500
    s 中所有字符都是小写字母。

题目评估

知识点:动态规划
难度:困难(虽然本题和昨天的题代码几乎一样,但是思考过程比较困难)

分析

现在我们有一个现成的字符串s,我们要通过插入一些字符让它变成回文,如何使插入的字符最少呢?要想插入的少,就要忽略已经是回文的子序列,OK!那么我们只要找到最长的回文子序列,再用字符串s的长度减去最长回文子序列的长度就是我们要插入的字符数量,因为我们只有再插入这么多字符,才能让整个字符串s变成回文!是不是和昨天的题有点类似?昨天的题就是找到一个字符串的最长回文子序列的长度。我们把昨天的方法拿过来用一下,答案就信手拈来了。

Java代码题解

class Solution {
    public int minInsertions(String s) {
		
    	// 如果长度为0或1直接返回0,因为不需要任何操作它本身就是回文
    	if (s == null || s.length() == 0 || s.length() == 1) {
    		return 0;
    	}
		
    	// 用该字符串本身的长度减去最长回文子序列就是本题的答案
    	int res = s.length() - longestPalindromeSubseq(s);
    	
    	return res;
    }
 
    public int longestPalindromeSubseq(String s) {  // 这是力扣第516题的题解
		
    	// 定义一个字符串长度*字符串长度的二维数组,用来保存子串的最大回文子序列长度
    	int[][] dp = new int[s.length()][s.length()];
    	
    	for (int i = dp.length - 1; i >= 0; i--) {        // i从最后一个开始遍历
			dp[i][i] = 1;  // 初始化,每个字符都是长度为一的回文
    		for (int j = i + 1; j < dp[i].length; j++) {  // j从第i+1个开始遍历
				if (s.charAt(i) == s.charAt(j)) {  // 如果子串的两头字符相等
					// 该子串掐掉两头后的子串最大子回文序列长度+2就是该子串的最大回文子序列长度
					dp[i][j] = dp[i + 1][j - 1] + 2;  
				} else {  // 如果该子串两头字符不相等
					// 该子串的两个掐掉一头的子串最大回文子序列长度,哪个最大,就取哪个赋给该子串最大回文子序列长度
					dp[i][j] = Math.max(dp[i][j - 1], dp[i + 1][j]);
				}
			}
		}
    	// 最后返回整个字符串的最大回文子序列长度
    	return dp[0][dp[0].length - 1];
    }
    
}
力扣1312题

复杂度分析

和昨天的题一样:
设n表示字符串长度,双层遍历一个二维数组,时间复杂度为O(n^2)
开辟了一个n*n的二维数组,空间复杂度为O(n^2)

# 算法 # 程序设计 # 动态规划
力扣516题-最长回文子序列-动态规划题解
力扣10题-正则表达式匹配
  • 文章目录
  • 站点概览
优律

优律

优律的知识库

83 日志
20 分类
44 标签
E-mail Twitter Instagram
Links
  • CZLisyx - 浮生志
  • Vedfolnir
0%
© 2019 — 2023 萤火小屋——优律的博客网站
网站已勉强运行 
Halo博客系统技术支持