文字列の圧縮

問題

文字列を圧縮する。同じ文字が続いた数を使って表現する。 例：abbccccddd -> a1b2c4d3 とする。ただし、圧縮した方が、文字数が増えている場合は元の文字列を変えす。

考え方

元の文字列を１つずつ進んでいく。sに文字を入れて、s == str[i]である時にcount++をして、s != str[i]となった時に、文字列にsとcountをappendする。

計算量

時間計算量はO(N)になります。空間計算量もO(N)ですね。

コード例

#include<iostream>
#include<sstream>
using namespace std;

string compression(string str){
    int i, j, count;
    string ans;
    string s = str.substr(0, 1);
    j = 0;
    for(i=0; i<str.length(); i++){
        if(s==str.substr(i, 1)){
            count++;
        }else{
            j += 2;
            ans += s;
            ans += to_string(count);
            s = str.substr(i, 1);
            count = 1;
        }
    }
    j += 2;
    ans += s;
    ans += to_string(count);
    if(j<str.length()){
        return ans;
    }else{
        // 圧縮した方が文字数多い時は元の文字列を返す
        return str;
    }
}

int main(void){
    string str = "aabadddcckkkk";
    cout << "元の文字列は " << str << endl;
    str = compression(str);
    cout << "できた文字列は" << str << endl;
    return 0;
}

参考

世界で闘うプログラミング力を鍛える本 | マイナビブックス