笔试-化简字符串

发表于 | 更新于

题目

滴滴笔试的题目，暂时没挂到牛客上。

题意

给出一个字符串，要求化简字符串，
如: ‘bcabcabc’ 这样的字符串会被化简为 ‘3[abc]’，
但是如果化简后的字符串比原串长度要长，则不化简。
化简可以嵌套，
比如：’abcdabcdeabcdabcdexyabcabcabcds’可以化简为’2[2[abcd]e]xy2[abc]ds’。
输出化简后的长度。

题解

枚举每个子串，求出每个子串后面连续相同的个数，然后替换成相应的简化形式。
一个字符串不一定只化简一次，所以加一层循环直到不能化简为止，取最短长度即可。

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <bits/stdc++.h>
using namespace std;

string intToStr(int num){
    string ans ="";
    while(num){
        ans += num%10+'0';
        num /= 10;
    }
    reverse(ans.begin(),ans.end());
    return ans;
}


string getSimple(string str){
    if(str.size() < 5) return str;

    for(int i=0;i<str.size();i++){
        for(int j=i+1;j<str.size();j++){
            string sub = str.substr(i,j-i);
            int start = j , reCount = 0;
            while(str.find(sub,start)==start){
                reCount++;
                start += j-i;
            }
            if(reCount==0) continue;
            string countStr = intToStr(reCount+1);
            if(reCount*(j-i)<countStr.size()+2) continue;
            string res = str.substr(0,i);
            res+=countStr;
            res+='[';
            string next = getSimple(sub);
            res+=next;
            res+=']';
            res+= str.substr(j+reCount*(j-i),str.size()-j+reCount*(j-i));
            return res;
        }
    }
    return str;
}

int main(){
    string str;
    cin>>str;
    int mixLen = str.size();
    string preStr = str;
    string ansStr = str;
    while(true){
        string ret = getSimple(preStr);
//        cout<<ret<<endl;
        if(ret == preStr) break;
        else preStr = ret;
        if(mixLen > ret.size()){
            mixLen = ret.size();
            ansStr = ret;
        }
    }
    cout<<ansStr<<endl;
    cout<<mixLen<<endl;
    return 0;
}