38_Count and Say

[Easy]

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

1
11
21
1211
111221

1is read off as"one 1"or11. 11is read off as"two 1s"or21. 21is read off as"one 2, thenone 1"or1211.

Given an integern, generate thenthterm 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"

Solution: iterative

Idea:

• The elements in the sequence are computed from the counting and saying for each number from previous element

• For each string in the sequence, loop over the whole string, count the frequence and record the letter, add into the output sequentially

Time Complexity: $O(2^n n)$ because the length of next string may be double of the length of previous string.

Space Complexity: $O(2^n)$ for the output

def countAndSay(n):
    """
    :type n: int
    :rtype: str
    """
    ret = '1'
    for i in range(1, n):
        ret_new = ''
        digit = ret[0]
        count = 0
        for cur in ret:
            if cur == digit:
                count += 1
            else:
                ret_new += str(count) + digit
                digit = cur
                count = 1    
        ret_new += str(count) + digit
        ret = ret_new
    return ret

Note:

然后在想这个过程的时候，你可能会想的比较复杂，比如，会不会出现连续十几个一样的数字，比如1111111111，读作“ten 1”，然后转换成101。实际上，有大神已经证明，这个序列里的数不会超过4。这边搬运了一下。 原链接：https://leetcode.com/discuss/6762/how-to-proof-the-count-is-always-less-than-10

Proof by exhaustion and contrapositive:

In order for a number greater than 4 to be created, there must be a series of numbers n>4 in length all the same digit. Therefore, there is a subset of that series where the count would only reach 4. Because of this, any proof for the existence of a chain resulting in a number greater than 4 is also a proof for the existence of a 4-chain. Using the proof by contrapositive, this means that if 4-chains are proved to be impossible, then any n-chain with n>4 is also impossible.

In order to start with a chain with numbers greater than 4, you must assume that a 4-chain is possible in the first place, which is circular reasoning, and so cannot be used as an initial point. It is further impossible to have a negative value, since the counting numbers do not include them.

Therefore, the only chains able to create a 4 (at least the first one) are 0000, 1111, 2222, or 3333.

0 0 0 0 -> 40 The 0000 is read zero 0, zero 0, which must come from . Since there is nothing present, it could in theory occur anywhere in the string. However, since they would be next to each other, if the 0 is repeated as would be neccessary, the zeros would add together, resulting in just zero 0, leaving only 20, not 40.

1 1 1 1 -> 41 The 1111 is read one 1, one 1 (or 11), which translates to 21, not 1111. This contradicts the assumption that there is a way to get 1111, and so prevents 4 or greater from appearing. Therefore, 1s cannot reach 4.

2 2 2 2 -> 42 The 2222 is read two 2, two 2 (or 22 22), which is identical to the output. Since the input maps to itself, there is no way to leave that cycle, or it already would have. If 2222 exists in the input, then 2222 must have mapped to it. It cannot reach 42. Therefore, 2s cannot reach 4.

3 3 3 3 -> 43 The 3333 is read three 3, three 3 (or 333 333). This in turn would require 333 333 333. This fails in two respects. First, that the previous inputs would not merge to 63 or 93. The second, that the sequence eventually traces back to the origin, 1. Since it keeps increasing in length as the number of rounds since the start decreases, it cannot have started at 1. Therefore, 3s cannot reach 4.

As every possible case has been examined, and none can reach a 4 while starting at the given beginning (1), it is not possible for a 4-chain to occur, meaning a 4 cannot appear in any valid string for this problem. Further, as stated above, since a 4-chain is impossible, so too are all n-chains with n>4, so no number greater than 4 can appear either.