LeetCode / Count and Say

https://leetcode.com/problems/count-and-say/

The count-and-say sequence is the sequence of integers with the first five terms as following:

1. 1
   
2. 11
   
3. 21
   
4. 1211
   
5. 111221

1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.

Given an integer n where 1 ≤ n ≤ 30, generate the nth term of the count-and-say sequence.

Note: Each term of the sequence of integers will be represented as a string.

Example 1:
Input: 1
Output: "1"

Example 2:
Input: 4
Output: "1211"

Bad評価が多い問題、、、確かに問題の意味が分かりにくいですね。日本語で補足すると以下のようになります。

1. 1 -> 初期値は1
   
2. 11 -> 前のステップの値が、1つの1から成るので、11
   
3. 21 -> 前のステップの値が、2つの1から成るので、21
   
4. 1211 -> 前のステップの値が、1つの2、1つの1から成るので、1211
   
5. 111221 -> 前のステップの値が、1つの1、1つの2、2つの1から成るので、111221

解答・解説

解法1

この問題は、地道にループを回す解法しかないのではないかと思います。以下の通り。

class Solution:
    def countAndSay(self, n: int) -> str:
        s = '1'
        # n-1回のループを回し、各ステップの出力を次のステップの入力とする
        for _ in range(n-1):
            # letがカウントする文字、cntがカウント数、tmpが(カウント数+カウントする文字)の文字列を一時的に格納する変数
            let, cnt, tmp = s[0], 0, ''
            # 文字列sの文字数分のループを回す
            for l in s:
                # 同じ文字が続いている場合はcntに+1するのみ
                if let == l:
                    cnt += 1
                # 異なる文字が来た場合はここまでの(カウント数+カウントする文字)をtmpに格納してlet,cntは初期化する
                else:
                    tmp += str(cnt)+let
                    let = l
                    cnt = 1
            tmp += str(cnt)+let
            s = tmp
        return s

解法2

Pythonであれば、組み込み関数が充実しているので他にも様々な解法があります。
例えば、itertoolsというiterableなデータ（リストなど）を任意のキーでグルーピングし、キーとキーに属する要素のイテレータを返す関数を使う方法。
itertoolsの挙動の例は、以下の通り。

s = '1211'
for d,i in itertools.groupby(s):
    print(d, list(i))
# ---> 1 ['1']
# ---> 2 ['2']
# ---> 1 ['1', '1']

これを使うと、以下のように書けます。

class Solution:
    def countAndSay(self, n):
        s = '1'
        for _ in range(n - 1):
            s = ''.join(str(len(list(group))) + digit for digit, group in itertools.groupby(s))
        return s
    return s