|
| 1 | +<h2><ahref="https://leetcode.com/problems/count-and-say">38. Count and Say</a></h2><h3>Medium</h3><hr><p>The <strong>count-and-say</strong> sequence is a sequence of digit strings defined by the recursive formula:</p> |
| 2 | + |
| 3 | +<ul> |
| 4 | +<li><code>countAndSay(1) = "1"</code></li> |
| 5 | +<li><code>countAndSay(n)</code> is the run-length encoding of <code>countAndSay(n - 1)</code>.</li> |
| 6 | +</ul> |
| 7 | + |
| 8 | +<p><ahref="http://en.wikipedia.org/wiki/Run-length_encoding"target="_blank">Run-length encoding</a> (RLE) is a string compression method that works by replacing consecutive identical characters (repeated 2 or more times) with the concatenation of the character and the number marking the count of the characters (length of the run). For example, to compress the string <code>"3322251"</code> we replace <code>"33"</code> with <code>"23"</code>, replace <code>"222"</code> with <code>"32"</code>, replace <code>"5"</code> with <code>"15"</code> and replace <code>"1"</code> with <code>"11"</code>. Thus the compressed string becomes <code>"23321511"</code>.</p> |
| 9 | + |
| 10 | +<p>Given a positive integer <code>n</code>, return <em>the </em><code>n<sup>th</sup></code><em> element of the <strong>count-and-say</strong> sequence</em>.</p> |
| 11 | + |
| 12 | +<p> </p> |
| 13 | +<p><strongclass="example">Example 1:</strong></p> |
| 14 | + |
| 15 | +<divclass="example-block"> |
| 16 | +<p><strong>Input:</strong> <spanclass="example-io">n = 4</span></p> |
| 17 | + |
| 18 | +<p><strong>Output:</strong> <spanclass="example-io">"1211"</span></p> |
| 19 | + |
| 20 | +<p><strong>Explanation:</strong></p> |
| 21 | + |
| 22 | +<pre> |
| 23 | +countAndSay(1) ="1" |
| 24 | +countAndSay(2) = RLE of"1" ="11" |
| 25 | +countAndSay(3) = RLE of"11" ="21" |
| 26 | +countAndSay(4) = RLE of"21" ="1211" |
| 27 | +</pre> |
| 28 | +</div> |
| 29 | + |
| 30 | +<p><strongclass="example">Example 2:</strong></p> |
| 31 | + |
| 32 | +<divclass="example-block"> |
| 33 | +<p><strong>Input:</strong> <spanclass="example-io">n = 1</span></p> |
| 34 | + |
| 35 | +<p><strong>Output:</strong> <spanclass="example-io">"1"</span></p> |
| 36 | + |
| 37 | +<p><strong>Explanation:</strong></p> |
| 38 | + |
| 39 | +<p>This is the base case.</p> |
| 40 | +</div> |
| 41 | + |
| 42 | +<p> </p> |
| 43 | +<p><strong>Constraints:</strong></p> |
| 44 | + |
| 45 | +<ul> |
| 46 | +<li><code>1 <= n <= 30</code></li> |
| 47 | +</ul> |
| 48 | + |
| 49 | +<p> </p> |
| 50 | +<strong>Follow up:</strong> Could you solve it iteratively? |