X

LEETCODE 1531. String Compression II 解题思路分析

题目大意:

压缩字符串 II

行程长度编码 是一种常用的字符串压缩方法,它将连续的相同字符(重复 2 次或更多次)替换为字符和表示字符计数的数字(行程长度)。例如,用此方法压缩字符串 “aabccc” ,将 “aa” 替换为 “a2″ ,”ccc” 替换为` “c3” 。因此压缩后的字符串变为 “a2bc3” 。

注意,本问题中,压缩时没有在单个字符后附加计数 ‘1’ 。

给你一个字符串 s 和一个整数 k 。你需要从字符串 s 中删除最多 k 个字符,以使 s 的行程长度编码长度最小。

请你返回删除最多 k 个字符后,s 行程长度编码的最小长度 。

示例 1:

输入:s = "aaabcccd", k = 2
输出:4
解释:在不删除任何内容的情况下,压缩后的字符串是 "a3bc3d" ,长度为 6 。最优的方案是删除 'b' 和 'd',这样一来,压缩后的字符串为 "a3c3" ,长度是 4 。

示例 2:

输入:s = "aabbaa", k = 2
输出:2
解释:如果删去两个 'b' 字符,那么压缩后的字符串是长度为 2 的 "a4" 

示例 3:

输入:s = "aaaaaaaaaaa", k = 0
输出:3
解释:由于 k 等于 0 ,不能删去任何字符。压缩后的字符串是 "a11" ,长度为 3 。

提示:

  • 1 <= s.length <= 100
  • 0 <= k <= s.length
  • s 仅包含小写英文字母

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1531

解题思路分析:

这两周比较忙(懒),都没赶上周赛,今天开始补作业。

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

s = "abacad";
k=2;

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

  1. 选择第一个a,即子序列的左半部分为a,右半部分需要在bacad中找到一个长度为3的并不以a开头的序列(递归求解)。
  2. 选择前两个a,即子序列的左半部分为aa,右半部分需要在cad中找到一个长度为2的并不以a开头的序列(递归求解)。
  3. 选择前三个a,即子序列的左半部分为aaa,右半部分需要在d中找到一个长度为1的并不以a开头的序列(递归求解)。

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

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

另外,递归方法一般都要有记忆数组相伴。递归函数的参数中,我们需要传递当前的index,即右半部分的起始位置,以及当前剩余长度count两个变量,因此使用一个二维记忆数组即可保存递归函数的转态(相当于动态规划解法中的DP数组)。这里,递归函数可以被描述为:从下标index开始向后,在所有长度为count的子序列中,找到编码后的最小长度并返回。

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

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

实现代码:

int[][] memo; // 记忆数组
public int getLengthOfOptimalCompression(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;
}

本题解法执行时间为78ms。

Runtime: 78 ms, faster than 79.09% of Java online submissions for String Compression II.

Memory Usage: 39.9 MB, less than 100.00% of Java online submissions for String Compression II.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1531-string-compression-ii-解题思路分析/
Categories: leetcode
kwantong: