题意

给定字符串,和最多可以先删除的字符数量,再对它进行连续字符的压缩,求压缩后字符串的最短长度

限制:

原字符串长度不大于100

方法

dfs(TLE)

题目拆解为两部分

1. 字符串删除
2. 压缩字符串

对于字符串删除字符的部分,采用深度搜索的方式, 每层记录,当前遍历的字符串位置,还可以删除的字符串个数,和删除后的字符串的部分

对于压缩字符串的部分,采取遍历和计数的方式来计算压缩后的字符串长度

以题目样例"aabcccccaaa"为例

代码

class Solution {
public:
    int zip(int cnt){
        if(cnt == 1){ // 一个字符
            return 1;
        }else if(cnt > 1 && cnt < 10){ // 一位数字符
            return 2;
        }else if(cnt > 9 && cnt < 100){ // 两位数字符
            return 3;
        }else if(cnt == 100){
            return 4;
        }
        return 0;
    }
    // 计算压缩后的长度
    int lenStr(string s){
        int ans = 0; // 总长度
        char ch = 0; // 当前字符
        int cnt = 0; // 累计个数
        for(int i = 0;i<s.length();i++){
            if(s[i] == ch){ // 字符相同
                cnt++; // 计数+1
            }else{ // 字符不同
                ans += zip(cnt); // 压缩之前的
                ch = s[i]; // 更新 字符
                cnt = 1;
            }
        }
        ans += zip(cnt);
        return ans;
    }
    
    int dfs(string &s,int idx,int k,string t){
        int r = s.length();
        if(idx == s.length()){
            return lenStr(t);
        }
        if(k){ // 删除这个字符
            r = min(r,dfs(s,idx+1,k-1,t));
        }
        return min(r,dfs(s,idx+1,k,t+s[idx]));  // 不删除这个字符
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @param k int整型 
     * @return int整型
     */
    int compressString(string s, int k) {
        // write code here
        return dfs(s,0,k,"");
    }
};

复杂度分析

时间复杂度: 对于压缩的时间复杂度为$O(n)O(n)$,但对于深搜,最坏情况,每个位置会存在删或不删,所以总时间复杂度为$O(2^n\cdot n)O(2^n\; \backslash cdot\; n)$

空间复杂度: 主要在于递归的深度和递归时产生的字符串的占用,所以空间复杂度为$O(n^2)O(n^2)$

递推

设计状态 dp[i][ch][j][k]=l当前位置i,同样的字符ch连续j个,删除了k个,压缩后长度为l

zip是用于计算压缩后的长度的函数

若上个状态是dp[i][ch][j][k] 那么当选择第i个字符时

如果ch==s[i]那么有 dp[i+1][s[i]][j+1][k] = dp[i][ch][j][k] + zip(j+1) - zip(j),

否则如果第i-1不是相同的字符 dp[i][s[i]][1][k] = dp[i][ch][j][k] + zip(1), 因为和前面的字符不同,所以不会和前面的一起被压缩,所以长度为1

对于删除第i个字符的请跨国你dp[i][ch][j][k+1] = dp[i][ch][j][k]

最后在i == s.length()中找最小值即可

代码

class Solution {
public:
    int zip(int cnt){
        if(cnt == 1){ // 一个字符
            return 1;
        }else if(cnt > 1 && cnt < 10){ // 2-位数字符
            return 2;
        }else if(cnt > 9 && cnt < 100){ // 两位数字符
            return 3;
        }else if(cnt == 100){
            return 4;
        }
        return 0;
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @param k int整型 
     * @return int整型
     */
    int compressString(string s, int k) {
        if(k == s.length())return 0;
        const int INF = 0x3f3f3f3f;
        // [i][ch][j][k]=l 当前位置i,同样的字符ch连续j个,删除了k个,压缩后长度为l
        // dp[i][j][k] = dp[i-1][j]
        vector<vector<vector<vector<int>> > > dp(
            s.length()+1,
            vector<vector<vector<int>>>(
                26,
                vector<vector<int>>(
                    s.length()+1,
                    vector<int>(s.length()+1,INF))));
        for(int i = 0;i<26;i++){ // 初始化
            dp[0][i][0][0] = 0;
        }
        for(int i = 0;i<s.length();i++){
            for(int ch = 0;ch<26;ch++){
                for(int j = 0;j<=i;j++){
                    for(int m = 0;m <= min(k,i);m++){
                        if(dp[i][ch][j][m] == INF)continue;
                        // 不删 i
                        if(s[i]-'a' == ch){ // 字符相同
                            dp[i+1][ch][j+1][m] = min(
                                dp[i+1][ch][j+1][m],
                                dp[i][ch][j][m] + zip(j+1)-zip(j)
                            );
                        }else{ // 字符不同
                            dp[i+1][s[i]-'a'][1][m] = min(
                                dp[i+1][s[i]-'a'][1][m],
                                dp[i][ch][j][m] + zip(1)
                            );
                        }
                        // 删 i
                        if(m < k){
                            dp[i+1][ch][j][m+1] = min(
                                dp[i+1][ch][j][m+1],
                                dp[i][ch][j][m]
                            );
                        }
                    }
                }
            }
        }
        int ans = INF;
        // 找最小值
        for(int ch = 0;ch<26;ch++){
            for(int j = 0;j<=s.length();j++){
                for(int m = 0;m <= k;m++){
                    ans = min(ans,dp[s.length()][ch][j][m]);
                }
            }
        }
        return ans;
    }
};

复杂度分析

时间复杂度: 主要是状态和状态转移,其中状态转移是常数$O(n^3)O(n^3)$

空间复杂度: 主要是状态存储$O(n^3)O(n^3)$