# 38. Count and Say
###### tags: `leetcode` `38` `medium`

## :memo: Question

## :memo: 題意
* 這題跟 fibonacci number 的做法一樣，

舉例：
n = 1, return "1"
"1" => one 1 => "11"
n = 2, countAndSay(2) = "11"
"11" => two 1 => "21"
n = 3, countAndSay(3) = "21"
"21" => one 2, one 1 = "1211"
n = 4, countAndSay(4) = "1211"
"1211" => one 1 one 2 two 1 = "111221"
n = 5, countAndSay(5) = "111221"

## 這邊要注意我們算到 n=4 的時候有看到 "1211" 不能標示為 three 1 one 2，他是有順序的。

## :memo: my first solution

class Solution:
    def countAndSay(self, n: int) -> str:
        if n == 1: return "1"
        if n == 2: return "11"
            
        dp = [""] * n
        
        dp[0] = "1"
        dp[1] = "11"
        
        for i in range(2, n):
            
            count = 0
            l = 0
            r = 0
            strings = ""
            while r < len(dp[i-1]):
                if dp[i-1][l] == dp[i-1][r]:
                    count += 1
                    r += 1
                elif dp[i-1][l] != dp[i-1][r] and l + 1 == r:
                    strings += str(count) + dp[i-1][l]
                    l += 1
                    count = 0
                else:
                    l += 1
            if count:
                strings += str(count) + dp[i-1][l]
            dp[i] = strings
            
            
        return dp[n-1]
    

## :memo: 檢討
* 原本寫的第一個版本速度其實很慢，我猜想應該是在 while 這邊我用兩個指針去算所以導致會花比較多時間，所以會從這邊著手改進，還有 dp 這個陣列感覺也是多餘的空間使用。

## :memo: faster solution

class Solution:
    def countAndSay(self, n: int) -> str:
        if n == 1: return "1"
        if n == 2: return "11"
        
        value = "11"
        temp = ""
        
        for i in range(2, n):
            
            count = 0
            strings = ""
            
            for i in range(len(value)):
                if i == 0:
                    count = 1
                    continue
                if value[i] == value[i-1]:
                    count += 1
                elif value[i] != value[i-1]:
                    strings += str(count) + value[i-1]
                    count = 1
                    
            if count:
                strings += str(count) + value[-1]
                
            temp = strings
            value, temp = temp, ""
            
        return value

## :memo: bigO
* 時間複雜度: O(sum(n)) n 每個字串的長度
* 空間複雜度: O(1)