CTDL và giải thuật - Mã hóa chuỗi

Cho một sâu s chỉ gồm các ký tự viết thường, hãy viết hàm trả về chuỗi mã hóa của sâu này. Xem ví dụ để hiểu rõ hơn quá trình mã hóa.

Ví dụ

  • Test mẫu 1:
     
    Input Output

    aaabbaaac

    a3b2a3c1

    Với s = "aaabbaaac" thì encodeString(s) = "a3b2a3c1".
     
  • Test mẫu 2:
     
    Input Output

    ab

    a1b1


    Với s = "ab" thì encodeString(s) = "a1b1".
     
  • Test mẫu 3:
     
    Input Output

    aaddacc

    a2d2a1c2

    Với s = "aaddacc" thì encodeString(s) = "a2d2a1c2".

Hướng dẫn bài tập.

Tạo một stack để lưu lần lượt các ký tự trong chuỗi s, nếu st.top() != s[i] thì kết quả sẽ thêm st.top() và số lượng phần tử trong st vào chuỗi kết quả.

Code mẫu:

Ngôn ngữ C++:

#include <iostream>
#include <stack>
#include <string>

using namespace std;

string to_string(long long n){
    string s = "";
    while (n > 0){
        s = char (n%10 + '0') + s;
        n /= 10;
    }
    return s;
}

int main(){
	string s;
	getline(cin, s);
 	s = s + '@';
    stack<char> st;
    string str = "";
    for (int i = 0; i < s.length(); i++){
        if (st.empty() || st.top() == s[i]){
            st.push(s[i]);
        } else {
            int count = 0;
            str = str + st.top();
            while(!st.empty()){
                count++;
                st.pop();
            }
            str = str + to_string(count);
            st.push(s[i]);
        }
    }
    cout << str;
}