压缩字符串IIJava

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

行程长度编码是一种常用的字符串压缩方法，它将连续的相同字符（重复 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 仅包含小写英文字母

# 思路

Arrays.fill

# 解法

class Solution {
    static final int INFINITY = Integer.MAX_VALUE / 2;

    public int getLengthOfOptimalCompression(String s, int k) {
        int n = s.length();
        int[][] dp = new int[n + 1][k + 1];
        for (int i = 1; i <= n; i++) {
            Arrays.fill(dp[i], INFINITY);
        }
        for (int i = 1; i <= n; i++) {
            char c = s.charAt(i - 1);
            int maxCompression = Math.min(i, k);
            for (int j = 0; j <= maxCompression; j++) {
                int deleteLength = j > 0 ? dp[i - 1][j - 1] : INFINITY;
                int noDeleteLength = INFINITY;
                int repeatCount = 0, deleteCount = 0;
                int digits = 0;
                for (int p = i; p > 0 && deleteCount <= j; p--) {
                    if (s.charAt(p - 1) == c) {
                        repeatCount++;
                        if (repeatCount == 2 || (repeatCount % 10 == 0 && (repeatCount - 1) % 9 == 0)) {
                            digits++;
                        }
                        noDeleteLength = Math.min(noDeleteLength, dp[p - 1][j - deleteCount] + 1 + digits);
                    } else {
                        deleteCount++;
                    }
                }
                dp[i][j] = Math.min(deleteLength, noDeleteLength);
            }
        }
        return dp[n][k];
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

# 总结

分析出几种情况，然后分别对各个情况实现

#Java