[演算法題目] Run-Length Encoding

本題資訊

難度：easy
使用語言：C++
相關概念：Strings

題目敘述

Write a function that takes in a non-empty string and returns its run-length encoding.

Input: AAAAAAAAAAAAABBCCCCDD

Output: 9A4A2B4C2D

這題要求處理字串，計算字母個數，改成字母個數+字母的形式儲存。若字母的個數大於九，例如上方例子有 13 個 A 的狀況，那麼我們會拆開成 9A4A 避免解碼錯誤。

這題以功用上來說，對於重複性很高的字串可有效壓縮空間。

• Run-length encoding

Idea

剛看到題目時，我想的蠻複雜的。一下要計算字母個數，計算完後要注意超過 9 就要分開，所以還用了兩個 while 去寫，結果還是錯的😒

後來突然注意到：當計數器到達 9 之後，就可以列印或儲存結果了，不需要整個完全計算後才處理，這樣重點就會回到條件判斷。

從頭開始巡覽，首先因為巡覽到的字母必有一個，計數器 count 一定是從 1 開始。
接著我希望能判斷目前走到的字母，若和前一個字母不一樣或是 count 已經等於 9，將目前的數目和字母儲存在 result 裡面，並且將 count 重設為 0。

若一樣則計數器 count 加一。

要注意的是，因為最後一個字母不會觸發儲存的條件，所以巡覽完後記得要把最後的結果再放去 result 中。

#include <vector>
using namespace std;

string runLengthEncoding(string str) {
  vector<char> result;
  int count = 1;

  for (int i = 1; i < str.size(); i++){
    if ((str[i] != str[i-1]) || count == 9){
      result.push_back(to_string(count)[0]);
      result.push_back(str[i-1]);
      count = 0;
    }
    count++;
  }
  result.push_back(to_string(count)[0]);
  result.push_back(str[str.size() - 1]);
  
  string newStr(result.begin(), result.end()); 
  return newStr;
}

時間複雜度：\(O(n)\)，\(n\) 是指字串長度。
空間複雜度：\(O(n)\)。