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ớis = "aaabbaaac"
thìencodeString(s) = "a3b2a3c1".
- Test mẫu 2:
Input Output ab
a1b1
Vớis = "ab"
thìencodeString(s) = "a1b1".
- Test mẫu 3:
Input Output aaddacc
a2d2a1c2
Vớis = "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;
}