文字列圧縮


中に入ると


KACA 2020ブラインドの求人で出た問題です.今回も文字列を切ってどうするかという質問カカオは文字列が好きらしい.
これこそ文字列を圧縮する問題で、最小長に圧縮できる方法を見つけなければなりません.aabbacccを例にとると、1つ(2 a 2 ba 3 c)を押圧すると、長さが最小となる.この方法は学校で習ったようです.1年生の教養課に通っていたのでよく覚えていませんが、文字列圧縮で似たようなことを学んだのは明らかです.
質問は質問の条件が重要です.難しくはありませんが、相談条件には関心がないのでウロウロ・・

コードの説明


まず、比較する文字の最大長文字列/2を変数cut sに保存します.比較する文字の長さがこれより大きければ、後の文字を比較しても同じ文字は出ないからです.
次は二重forゲートを回します.ここで最初のfor文はiが1からcut sに含まれるまでである.iは文字分割の基準であるため、0ではなく1からcut sと定義する必要があります.そして、標準となる文字列を0からi個切り出す.
次はjがiからs.length()に戻るfor文です.ここで気をつけて!単純にj++を作ることはできません.なぜなら、i文字を切り取ると仮定し、後で比較する文字列は切り取った文字列であるからです.例えば「aabb」の文字列を半分に切るときは、「aa」と「bb」をつけ、「aa」と「ab」をつけてはいけません.私はただ簡単にj++を作っただけで、間違った方法で切ったので、完全な答えはありません.
したがって、tmpで切断された文字列の後ろのiの長さが、基準となる文字列が一時的に切断された文字列と同じである場合、count++を使用することができる.異なる場合は、countが1より大きい場合にのみ、countをstringに変換してtmp allに貼り付け(countが1の場合は1を省略)、残りの基準を貼り付けます.standardにtmpの値を入れるのを忘れないでください.elseに移動し、tmpを表す文字列が標準と異なる場合は、標準をtmpに変換する必要があります.次にcountを1に初期化します.
sを最後に回転する場合は、すぐにサイズを比較するのではなく、残りの文字列を追加します.countが1より大きいかどうかを確認してから計算することもあります.最後に、tmp allの長さがresponse(sの長さ)より小さい場合、responseにtmp allの長さを入れることができる.
では、答えを求めればいいです!

コードの説明

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int solution(string s) {
    int answer = s.length();
    string s_answer = s;
    int count = 1;
    string tmp_all = "";
    string tmp = "";
    
    int cut_s = s.length()/2;
    
    for(int i=1; i<=cut_s; i++){    
        tmp_all = "";
        tmp = "";
        count = 1;
        string standard = s.substr(0, i);
    
        for(int j=i; j<s.length(); j+=i){
            tmp = s.substr(j, i);
            
            if(standard == tmp){
                count++;
                //cout << standard << " " << tmp << endl;
            }else{
                if(count > 1){
                    tmp_all += to_string(count);
                }
                tmp_all += standard;
                standard = tmp;
                count = 1;
            }
        }
        
        if(count > 1){
            tmp_all += to_string(count);
        }
        
        tmp_all += standard;

        //cout <<i << " " << tmp_all << endl;
        
        if(answer > tmp_all.length()){
            answer = tmp_all.length();
        }

    }
        return answer;
}