当前位置: 代码迷 >> 综合 >> 算法题解:求删除字符串的最少删除次数(Delete Steps)—JAVA代码
  详细解决方案

算法题解:求删除字符串的最少删除次数(Delete Steps)—JAVA代码

热度:45   发布时间:2024-01-15 19:14:48.0

问题描述

给定一个字符串str,允许删除相同的连续字符。你的任务是找到完全删除字符串所需的最小操作数。

例如:给定字符串 str = “abcddcba”
输出结果为: 4
删除 dd, 字符串变为: “abccba”
删除 cc, 字符串变为: “abba”
删除 bb, 字符串变为: “aa”
删除 aa, 字符串变为: null

所以,删除字符串的最少删除次数为:4 次

例如:给定字符串 str = “abc”
输出结果为:3


算法分析

采用动态规划算法。

设定一个dp数组,令 dp[m][n] 表示删除字符串 str[ m,m+1,m+2,...n ] 的最少删除次数,即为我们需要获得的答案。

我们会有两种情况:

  • 子字符串的第一个字母与其余字母分开删除,然后dp[m][n]=1+dp[m+1][n]。
  • 子字符串的第一个字母与其他字母一起删除(两个字母必须相等),然后dp[m][n]=dp[m+1][n-1]+dp[i][n],前提是m≤i≤n和s[i]=s[m]。

算法设计

package com.bean.algorithm.dp;public class MinimumStepsofDeleteCharacters {static int findMinimumDeletion(int m, int n, int dp[][], String s) {if (m > n) {return 0;}