题解 | #压缩字符串(二)#

题目主要信息

给定一个字符串，要求在删除k个字符的情况下，使得字符串的长度最短。

方法一：递归加记忆数组

具体方法

将本题的描述换一种说法，实际上是让我们从字符串s中找到一个长度为length(s)-k的子序列，其行程长度编码的长度最短。我们可以将该子序列分成两部分，左半部分为1个或者多个连续相同字符c，右半部分为不以c开头任意子序列。分别求出左右两部分的编码长度，求和即是当前子序列编码后的长度。而右半部分我们又可以差分为两部分，他的左半部分为1个或者多个连续相同字符c'(c’!=c)，它的右半部分不以c’开头任意子序列。以此类推，这实际上是一个清晰的递归过程。我们举例来看，比如：

$s = " a b a c a d "$ ;

$k = 2$ ;

因为k等于2，也就意味着我们需要在s中找到一个长度为4的子序列。我们从s下标为0处向后循环，当前字母为a，首先构建子序列的左半部分，即找到n个相同的a，对于本例，我们有三种选择方案：

选择第一个a，即子序列的左半部分为a，右半部分需要在bacad中找到一个长度为3的并不以a开头的序列（递归求解）。

选择前两个a，即子序列的左半部分为aa，右半部分需要在cad中找到一个长度为2的并不以a开头的序列（递归求解）。

选择前三个a，即子序列的左半部分为aaa，右半部分需要在d中找到一个长度为1的并不以a开头的序列（递归求解）。

除了上述三种情况，我们还可以向后查找以b开头或者以c开头的左半部分，所有选择中，编码后最短的子序列的长度即是返回结果。

总结来看，递归方法中我们需要使用到两层循环，第一层循环用来找到子序列左半部分的开头字母，第二层循环来控制该字母在子序列中连续出现的次数，也就是左半部分的长度。而右半部分交给递归子问题去处理。所有组合中，长度最短的即为当前递归的返回结果。

另外，递归方法一般都要有记忆数组相伴。递归函数的参数中，我们需要传递当前的index，即右半部分的起始位置，以及当前剩余长度两个变量，因此使用一个二维记忆数组即可保存递归函数的转态（相当于动态规划解法中的DP数组）。

最后再看下可以优化的部分，第一层循环，我们在找左半部分的开头字母，因此循环中遇到已经出现过的字母时可以跳过。比如上例中的字符串abacad，我们从下标0向后循环，按照顺序先找以a开头的左半部分，接下来是以b开头，在接下来又是字母a，这里我们没有必要再做重复操作，从当前下标2开始做第二层循环与下标0处唯一的区别是，子序列左半部分的a的最大长度只能达到2，而这种情况已被下标0处的情况所包含。解题时，我们可以考虑使用一个访问数组来记录我们已经处理过的字母。 alt

剩下的细节操作详见代码注释。

代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @param k int整型 
     * @return int整型
     */
    int[][] memo; // 记忆数组
    public int compressString(String s, int k) {
        memo=new int[s.length()][s.length()-k+1]; // 初始化记忆数组
        return help(s.toCharArray(), 0, s.length()-k); // 递归求解
    }
// 求从下标index开始向后，所有长度为count的子序列中，编码后的最小长度
    int help(char[] arr, int index, int count){
        if(count==0) return 0; // 子序列长度为0，返回0
        if(index==arr.length){ // 当下标越界时还未找到长度为count的子序列
            // 返回一个最大值，代表未找到合理解
            return Integer.MAX_VALUE;
        }
        // 如果记忆数组中存在数值，直接返回
        if(memo[index][count]>0) return memo[index][count];
        int min=Integer.MAX_VALUE; // 当前最优解
        boolean[] used = new boolean[26]; // 记录已经处理过的开头字母
        // 从index向后循环，寻找左半部分的开头字母
        for(int i=index;i<arr.length;i++){
            if(used[arr[i]-'a']) continue; // 优化：已处理过当前的字母，跳过
            // 优化：如果当前字母与上层递归的左半部分相同，跳过
            if(index>0&&arr[i]==arr[index-1]) continue;
            used[arr[i]-'a']=true; // 设当前字母已被处理过
            int leftCount=0; // 左半部分长度
            // 从当前下标开始向后循环，寻找相同字符（可不连续）
            for(int j=i;j<arr.length;j++){
                if(arr[j]!=arr[i]) continue; // 如果字符不相同，跳过
                leftCount++; // 左半部分长度(相同字符个数)加一
                if(count-leftCount<0) break; // 如果左半部分长度大于子序列长度，退出
                int left=getLength(leftCount); // 计算左半部分编码后长度
                int right=help(arr,j+1,count-leftCount); // 递归求解右半部分编码长度
                if(right==Integer.MAX_VALUE) continue; // 若递归返回值为最大值，代表不和理解，跳过
                int length=left+right; // 左右长度相加为当前子序列编码后长度
                min=Math.min(min, length); // 更新最小值
            }
        }
        memo[index][count]=min; // 将最小值存入记忆数组
        return min;
    }
    // 计算左半部分编码后长度
    // num：相同字符数量
    int getLength(int num){
        // 如果只有一个字母，返回长度1
        if(num==1) return 1;
        // 编码后长度，1代表字母占位长度
        int length=1;
        // 求num的位数
        while(num>0){
            length++;
            num/=10;
        }
        return length;
    }
}

复杂度分析

时间复杂度： $O （ n^{2} k ）$ ，三层循环
空间复杂度： $O （ n^{2} ）$ ，mem数组大小

方法二：动态规划（优化）

具体方法

状态 $d p [i] [j]$ 表示前i个字符删除j个后的长度

对于要求的 $d p [i] [j]$ 他的大小我们可以对第i个字符进行讨论

删除第i个字符, $d p [i] [j]$ 转移为 $d p [i - 1] [j - 1] .$

保留第i个字符,向前寻找相同的字符,并且认为有个下标为l的相同字符,使l到i连续,为了使l到i连续需要删除其中 $d e l$ 个字符, $d e l < = j$ .

$d p [i] [j]$ 为,找出所有符合条件的下标l求 $d p [l - 1] [j - d e l]$ +连续字符的长度的最小值.

代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @param k int整型 
     * @return int整型
     */
    public int compressString (String s, int k) {
        // write code here
        int n = s.length();
        int[][] dp = new int[n + 1][k + 1];
        for(int[] x:dp){
            Arrays.fill(x,n+1);
        }
        dp[0][0]=0;
        for(int i=1;i<=n;i++){
            for (int j=0;j<=i&&j<=k;j++){
                if(j<k) dp[i][j+1]=Math.min(dp[i-1][j],dp[i][j+1]);
                int del=0;
                for(int l=i;l>0;l--){
                    if(s.charAt(l-1)!=s.charAt(i-1)){
                        if(++del>j){  //计算需要删除个数
                            break;
                        }
                    } else {  //若删除del长，则dp[i][j]=dp[l-1][j-del]+len(i-l+1-del)+1
                        dp[i][j]=Math.min(dp[l-1][j-del]+len(i-l+1-del)+1,dp[i][j]);
                    }
                }
            }
        }
        return dp[n][k];
    }
    public int len(int k){
        if(k <= 1) return 0;
        else if(k > 1 && k < 10) return 1;
        else if(k >= 10 && k < 100) return 2;
        else return 3;
    }
}

复杂度分析

时间复杂度： $O （ n^{2} k ）$ ，三层循环
空间复杂度： $O （ n k ）$ ，状态储存