3種解法 - 實作字元串壓縮

題目

解法一（臨時變量）

解法二（快慢指針）

解法三（Pythonic)

字元串壓縮。利用字元重複出現的次數，編寫一種方法，實作基本的字元串壓縮功能。比如，字元串aabcccccaaa會變為a2b1c5a3。若“壓縮”後的字元串沒有變短，則傳回原先的字元串。你可以假設字元串中隻包含大小寫英文字母（a至z）。

示例1:

輸入：“aabcccccaaa”

輸出：“a2b1c5a3”

示例2:

輸入：“abbccd”

輸出：“abbccd”

解釋：“abbccd"壓縮後為"a1b2c2d1”，比原字元串長度更長。

提示：

字元串長度在[0, 50000]範圍内。

思路：使用臨時變量儲存上一次的字元，用目前字元進行判斷并計數，遇到新字元時重新記錄，這種寫法還是比較濃厚C的寫法，因為臨時的整型變量可能會重新申請對象。

記錄首個字元，使用清單儲存每次拼接的壓縮字元

對目前字元判斷，如果跟之前相同就計數，否則重新記錄字元

将最後一個字元加入list

時間複雜度：O(n)

空間複雜度：O(n)

思路：跟解法一思路類似，做法上通過兩個指針實作，慢指針始終指向字元開始位置，快指針指向相同字元的結束位置。

使用開始索引定位目前字元，一直通路字元串，直到開始位置到達字元串結尾

結束索引先到達字元串結尾時，由于開頭字元還未到達，是以會進入else子產品進行拼接

思路：利用python自身的庫函數itertools.groupby進行字元串歸類和統計

使用庫函數擷取字元串

使用三元運算傳回結果