<p>The <strong>count-and-say</strong> sequence is a sequence of digit strings defined by the recursive formula:</p>

<ul>
	<li><code>countAndSay(1) = &quot;1&quot;</code></li>
	<li><code>countAndSay(n)</code> is the run-length encoding of <code>countAndSay(n - 1)</code>.</li>
</ul>

<p><a href="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>&quot;3322251&quot;</code> we replace <code>&quot;33&quot;</code> with <code>&quot;23&quot;</code>, replace <code>&quot;222&quot;</code> with <code>&quot;32&quot;</code>, replace <code>&quot;5&quot;</code> with <code>&quot;15&quot;</code> and replace <code>&quot;1&quot;</code> with <code>&quot;11&quot;</code>. Thus the compressed string becomes <code>&quot;23321511&quot;</code>.</p>

<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>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">n = 4</span></p>

<p><strong>Output:</strong> <span class="example-io">&quot;1211&quot;</span></p>

<p><strong>Explanation:</strong></p>

<pre>
countAndSay(1) = &quot;1&quot;
countAndSay(2) = RLE of &quot;1&quot; = &quot;11&quot;
countAndSay(3) = RLE of &quot;11&quot; = &quot;21&quot;
countAndSay(4) = RLE of &quot;21&quot; = &quot;1211&quot;
</pre>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">n = 1</span></p>

<p><strong>Output:</strong> <span class="example-io">&quot;1&quot;</span></p>

<p><strong>Explanation:</strong></p>

<p>This is the base case.</p>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 30</code></li>
</ul>

<p>&nbsp;</p>
<strong>Follow up:</strong> Could you solve it iteratively?
class Solution { 
    public: 
    void st_to_array(string st,int num_, unordered_map<int,vector<vector<int>>>&res){
        int i=0; 
        vector<vector<int>> tmp;

        std::cout<<st<<std::endl;
        while(i<st.size()){ 
            int count=1; 
            int num=st[i++]-48; 
            //std::cout<< num <<std::endl;
            for(;i<st.size()&&st[i]-48==num;count++,i++); 
            vector<int>temp; 
            temp.push_back(num); 
            temp.push_back(count); 
            
            tmp.push_back(temp);
            std::cout<<"num " <<num <<"  count"<< count<<std::endl;
        } 
        res[num_]=tmp;

    } 
    string array_to_string(vector<vector<int>> num){
        string res=""; 
        for(auto pair:num){
            std::cout << "()"<<pair[0]<< ","<<pair[1]<<std::endl;
            int count=pair[1]; 
            //while(count){ 
                res+=to_string(pair[1]); 
                //count--; 
            res+=to_string(pair[0]);
            //} 
        } 
        std::cout<<"res: "<<res<<std::endl;
        return res;
    } 
    string countAndSay(int n) {
        //for(int i=1; i<n;i++){
        unordered_map<int,vector<vector<int>>>res;
        st_to_array("1",1,res); 
        for(int i=2;i<n+1;i++){ 
            //std::cout<<"i: "<< i <<" "<<array_to_string(res[i-1])<<std::endl;
                    st_to_array(array_to_string(res[i-1]),i,res); 
                            }
        if(n==1){
            return "1";
        }
        return array_to_string(res[n-1]);
    } 
};
28778