首页 > 试题广场 >

最短字符编码

[编程题]最短字符编码
  • 热度指数：844 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
给定一个非空字符串, 按照如下方式编码, 使得编码后长度最小, 返回编码后的长度: 
编码规则为: k[encoding_string], 表示重复k次encoding_strng, 
例如'abcdefabcdefabc'可表示为'2[abcdef]abc', 但是'aaa'仅能编码成'aaa', 
因为len('3[a]')>len('aaa').
补充:
1. k为正整数, []内的encoding_string不得含有空格不得为空;
2. []内的encoding_string 本身可以为编码过的字符串, 例如'abcdabcdeabcdabcde' 可以编码为 '2[abcdabcde]'(编码后长度从18减少到12), []内的'abcdabcde'又可以编码为 '2[abcd]e', 最终编码为 '2[2[abcd]e]', 编码后长度为11, 应返回11; 这个编码路径也能是: 'abcdabcdeabcdabcde' -> '2[abcd]e2[abcd]e' -> '2[2[abcd]e]';
2. 输入字符串为全小写英文字母, 长度<=160;
3. 如果编码后长度没有更小, 则保留原有字符串;

输入描述:
一行数据, 表示输入字符串


输出描述:
输出一个字符串表示编码后长度
示例1

输入

aaa

输出

3

说明

aaa，长度3
示例2

输入

aaaaa

输出

4

说明

5[a]，长度4
示例3

输入

aabcaabcd

输出

8

说明

2[aabc]d，长度8
算法知识视频讲解
添加回答
ABCNB头像 ABCNB
# 给出本题的python版本，供大家参考
def str_pro(s):
    len1 = len(s)   # 字符串长度
    len2 = len1 // 2   # 初始连续字符长度，最大为字符串长度的一半，由大到小递减
    if len1 <= 4:  # 如果字符串长度小于4，长度不会缩减，直接返回
        return s
    global best_count # 最优循环次数
    best_count=1
    global bset_len # 最优缩减后字符长度
    best_len=len1
    while (len2 >= 1): # 循环字符最小长度为1
        for i in range(0, len1 - len2 * 2 + 1): # 循环字符的起始位
            count = 1 # 记录循环次数
            s1 = s[i:i + len2] # 循环字符串
            s2 = s[i + len2:i + len2 * 2] # 他后面相同长度字符串
            while (s1 == s2):
                count += 1
                if i + len2 * (count + 1) <= len1: # 不能超界
                    s2 = s[i + len2 * count:i + len2 * (count + 1)]
                else:
                    break
            newline=len1-len2*count+len(str(count))+2+len2 # 新的字符串长度
            if count > 1 and newline < best_len: # 和当前最优比较
                best_len=newline # 更新
                best_count=count
                pre = s[:i] # 将新的字符串分为 前串  循环字符串  后串
                cur = s[i:i + len2]
                lat = s[i + len2 * count:]
        len2 -= 1 # 循环字符串长度减1
    if best_count==1: # 未缩减
        return s
    # 前串  循环字符串  后串 分别递归
    return str_pro(pre) + str(count) + '[' + str_pro(cur) + ']' + str_pro(lat)


if __name__ == '__main__':
    s = input()
    result = str_pro(s)
    print(len(result))
发表于 2018-09-29 17:46:27 回复(0)
C/C++
nbgao头像 nbgao 
#include <bits/stdc++.h>
using namespace std;

string F(string s){
    if(s.length() <= 4)
        return s;
    int n=s.length(), m=n/2, cnt=0, Min=INT_MAX;
    string pre, cur, lat;
    while(m>=1){
        for(int i=0;i<=n-m;i++){
            int t = 1;
            string a = s.substr(i, m), b;
            for(int j=1;j*m+m<=n;j++){
                b = s.substr(i+j*m, m);
                if(a == b)
                    t++;
                else
                    break;
            }
            int l = (n-t*m) + 3 + m;
            if(l<n && l<Min && t>1){
                Min = l;
                cnt = t;
                pre = s.substr(0, i);
                cur = s.substr(i, m);
                lat = s.substr(i + t*m);
            }
        }
        m--;
    }
    if(cnt==0)
        return s;
    return F(pre) + to_string(cnt) + "[" + F(cur) + "]" + F(lat);
}

int main(){
    string s, r;
    cin>>s;
    r = F(s);
    printf("%ld\n", r.length());
    return 0;
}

发表于 2020-11-07 01:38:28 回复(0)
哦哦哦5头像 哦哦哦5

每次递归找到压缩程度最好的结果。找到的重复的子串可能会将原子串分为3段

#include <bits/stdc++.h>
using namespace std;

string encoding_string(string s)
{
    if (s == "")return "";
    if (s.size() <= 4)return s;

    int len = s.size();
    int len2 = len / 2;    //重复子串的最大长度 可以分成的份数至少要2份

    int best_count = 0;//一次遍历得到的最优重复数
    int best_len = INT_MAX;//一次遍历得到的最优压缩到的长度
    string pre, cur, lat;//一次遍历得到的最优子串

    while (len2 >= 1)//重复子串长度最小为1
    {
        for (int k = 0; k <= len - len2; k++)//从第k个下标开始找重复子串
        {
            int count = 1;
            string s2 = s.substr(k, len2);
            string s3, s4;
            for (int j = 1; len2 * j + len2 <= len; j++)
            {
                s3 = s.substr(k + len2 * j, len2);
                if (s2.compare(s3) == 0 && s2.size() == s3.size())
                    count++;
                else
                    break;
            }

            int newlen = (len - count * len2) + 3 + len2;//压缩后的字符串长度
            if (newlen < len && newlen < best_len && count > 1)//如果压缩有效
            {
                best_len = newlen;
                best_count = count;
                pre = s.substr(0, k);
                cur = s.substr(k, len2);
                lat = s.substr(k + count * len2);
            }

        }
        len2--;//重复字符串长度缩短1
    }

    if (best_count == 0)
        return s;

    return encoding_string(pre) + to_string(best_count) + "[" + encoding_string(cur) + "]" + encoding_string(lat);
}
int main()
{
    string s;
    cin >> s;

    string result = "";
    result = encoding_string(s);

    cout << result.size() << endl;

    return 0;
}
编辑于 2018-08-21 11:18:04 回复(5)
╭(′•o•′)╭☞就是这个人！头像 ╭(′•o•′)╭☞就是这个人！ 
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        String res=in.nextLine();
        String result=encode(res);
        System.out.println(result.length());


    }

    static String encode(String s){
        if(s.length()<=4)return s;
        int len=s.length();
        int len2=len/2;
        int best_length=Integer.MAX_VALUE;
        int best_count=0;
        String pre="",cur="",pos="";

        while(len2>=1){
            for(int i=0;i<=len-len2;i++){
                int count=1;
                String s2=s.substring(i,i+len2);
                for(int j=1;i+len2*j+len2<=len;j++){
                    String s3=s.substring(i+len2*j,i+len2*j+len2);
                    if(s3.compareTo(s2)==0)count++;
                    else break;
                }
                int newLength=(len-len2*count)+len2+2+String.valueOf(count).length();
                if(newLength<len&& newLength<best_length&&count>1){
                    best_length=newLength;
                    best_count=count;
                    pre=s.substring(0,i);
                    cur=s2;
                    pos=s.substring(i+len2*count);
                    //System.out.println("最长字串"+cur);
                }
            }
            len2--;

        }
        if(best_count==0)return s;
        //System.out.println(encode(pre)+String.valueOf(best_count)+"["+encode(cur)+"]"+encode(pos));
        return encode(pre)+String.valueOf(best_count)+"["+encode(cur)+"]"+encode(pos);
    }
}
//按照评论区改写的java版本

编辑于 2021-05-12 16:28:35 回复(1)
codewind头像 codewind
这个题 怎么 a 啊
发表于 2021-01-10 21:42:00 回复(0)
Honoka201908082346878头像 Honoka201908082346878
Python 记忆化递归方法 
class Solution:
    def __init__(self):
        self.*** = {}
    def encode(self, s):
        if len(s) < 5:
            return s
        if s in self.***:
            return self.***[s]

        sl = len(s)
        mid = sl // 2
        ans = s
        for i in range(1, mid + 1):
            j, cnt, match = i, 1, s[:i]
            while match == s[j:j+i]:
                cnt += 1
                j += i
                sol = "{}[{}]{}".format(cnt, self.encode(match), self.encode(s[j:]))
                if len(sol) < len(ans):
                    ans = sol
                if i+j > sl: break
        nex = s[0] + self.encode(s[1:])
        if len(nex) < len(ans):
            ans = nex
        self.***[s] = ans
        return ans
s = input()
print(len(Solution().encode(s)))


发表于 2019-08-27 17:05:14 回复(0)
呃嗯头像 呃嗯 
#include<bits/stdc++.h>
using namespace std;
string encode(string s) {
        int lenth = s.size();
        vector<vector<string>> dp(lenth,vector<string>(lenth,""));
        for(int step=1;step<=lenth;step++){
            for(int i=0;i+step-1<lenth;i++){
                int j=i+step-1;
                dp[i][j]=s.substr(i,step);
                for(int k=i;k<j;k++){
                    string left = dp[i][k];
                    string right = dp[k+1][j];
                    if(left.size()+right.size()<dp[i][j].size()){
                        dp[i][j]=left+right;
                    }
                }
                string t = s.substr(i,j-i+1),replace="";
                auto pos = (t+t).find(t,1);
                if(pos>=t.size()) replace=t;
                else replace = to_string(t.size() / pos) + '[' + dp[i][i + pos - 1] + ']';
                if(replace.size()<dp[i][j].size()) dp[i][j]=replace;
            }
        }
        return dp[0][lenth-1];
}

int main(){
    string s;
    cin>>s;
    cout<<encode(s).length()<<endl;
}

发表于 2019-08-17 23:20:12 回复(0)
鱼忘七秒我忘七年头像 鱼忘七秒我忘七年 
#include<cstdio>
#include<iostream>
#include<cstring>
#define N 170
using namespace std;
int f[N][N],n;char s[N];
bool ok(int x1,int y1,int x2,int y2){//[x1,y1][x2,y2]分别是左右两半区间 
    int t=(y2-x2+1)/(y1-x1+1),le=y1-x1+1;//t=len2/len1,le=len1 
    if((y2-x2+1)%(y1-x1+1))return false;//两者连长度都不成比例，更不会有关系 
    for(int i=1;i<=t;i++)//第二段区间的长度是第一段区间长度的整t倍 
        for(int j=1;j<=le;j++)//枚举第一段区间的所有位 
            if(s[x1+j-1]!=s[(i-1)*le+x2+j-1])return false;//依次检验是否匹配 
    return true;
}
int get(int t){
    int p=0;
    while(t){t/=10;p++;}
    return p;
}
int dfs(int l,int r){
    if(l==r)return 1;
    if(l>r)return 0;
    if(f[l][r])return f[l][r];
    int t=r-l+1;//这段区间的长度 
    for(int i=l;i<r;i++){//枚举分割点 
        t=min(dfs(l,i)+dfs(i+1,r),t);
        if(ok(l,i,i+1,r))t=min(t,dfs(l,i)+2+get((r-i)/(i-l+1)+1));
        //如果符合条件，得到一个目前最短长度 
        //+1是因为要加上左侧一字符串 
    }
    return f[l][r]=t;
}
int main(){
    //freopen("jh.txt","r",stdin);
    scanf("%s",s+1);n=strlen(s+1);
    printf("%d",dfs(1,n));
    return 0;
}
编辑于 2018-09-05 18:55:45 回复(0)
提交观点

问题信息

C++工程师 iOS工程师 安卓工程师 运维工程师 字符串 前端工程师 算法工程师 测试工程师 PHP工程师 滴滴 自动驾驶/地图融合 系统工程师 模拟 测试开发工程师 2018 Java工程师
上传者：小小
难度：
8条回答 7082浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号