Welcome to Subscribe On Youtube

Question

Formatted question description: https://leetcode.ca/all/38.html

The count-and-say sequence is a sequence of digit strings defined by the recursive formula:

  • countAndSay(1) = "1"
  • countAndSay(n) is the way you would "say" the digit string from countAndSay(n-1), which is then converted into a different digit string.

To determine how you "say" a digit string, split it into the minimal number of substrings such that each substring contains exactly one unique digit. Then for each substring, say the number of digits, then say the digit. Finally, concatenate every said digit.

For example, the saying and conversion for digit string "3322251":

Given a positive integer n, return the nth term of the count-and-say sequence.

 

Example 1:

Input: n = 1
Output: "1"
Explanation: This is the base case.

Example 2:

Input: n = 4
Output: "1211"
Explanation:
countAndSay(1) = "1"
countAndSay(2) = say "1" = one 1 = "11"
countAndSay(3) = say "11" = two 1's = "21"
countAndSay(4) = say "21" = one 2 + one 1 = "12" + "11" = "1211"

 

Constraints:

  • 1 <= n <= 30

Algorithm

The algorithm is very simple, that is, for the previous number, find the number of the same element, and store the number and the element in the new string.

Code

  • 
    public class Count_and_Say {
    
        public String countAndSay(int n) {
    
            // @note: possibly overflow is n is large enough
            if(n <= 0) {
                return "";
            }
    
            String result = "1";
    
            while(n > 1) {
                char prev = result.charAt(0);
                int count = 1;
                String say = "";
    
                int i = 1;
                for(; i < result.length(); i++) {
                    char current = result.charAt(i);
    
                    if (current == prev) {
                        count++;
                    } else {
                        say += count + "" + prev;
    
                        // reset count
                        count = 1;
                        prev = current;
                    }
    
                }
    
                // check for last digit say
                say += count + "" + prev;
    
                result = say;
                n--;
            }
    
            // @note: string to int api: Integer.valueOf(result)
            return result;
        }
    
    
    	/*
    	 * @note:
    	 *
    	 * 		这道题非常的tricky
    	 * 		String的 += "x"的操作是比较expensive的,StringBuilder比较省
    	 *
    	 * 	StringBuilder的编译效率更高
    	 * 	ref:
    	 * 		http://stackoverflow.com/questions/14927630/java-string-concat-vs-stringbuilder-optimised-so-what-should-i-do
    	 *
    	 * 		注意坑,就是每次for loop完了之后,还有最后的一个count和say要加到结果里
    	 */
    	public class Solution {
    
    	    StringBuilder sb = new StringBuilder();
    
    	    // my thought, use iteration
    	    public String countAndSay(int n) {
    
    	        sb.append("1");
    
    	        StringBuilder newsb = new StringBuilder();
    
    	        for (int i = 1; i < n; i++) {
    
    	            // go through this string
    	            char previous = sb.charAt(0);
    	            int count = 1;
    
    	            // // add checking first input "1"...
    	            // if (sb.length() == 1) {
    	            //     sb.append(count);
    	            //     sb.append(previous);
    	            // }
    
    
    	            for (int j = 1; j < sb.length(); j++) {
    
    	                char curr = sb.charAt(j);
    
    	                if (curr == previous) {
    	                    count++;
    	                }
    	                // else if (curr != previous && j != sb.length() - 1) {
    	                else {
    	                    // sayIt(count, previous);
    	                    newsb.append(count);
    	                    newsb.append(previous);
    
    	                    // update
    	                    previous = curr;
    	                    count = 1;
    	                }
    	                // else {
    	                //     // sayIt(count, previous);
    	                //     newsb.append(count);
    	                //     newsb.append(previous);
    	                // }
    	            }
    
    	            // append the last one
    	            newsb.append(count);
    	            newsb.append(previous);
    
    	            // update sb
    	            sb = new StringBuilder(newsb);
    	            // @note: sb has NO clear()
    	            // newsb.clear();
    	            newsb = new StringBuilder();
    	        }
    
    	        return sb.toString();
    	    }
    	}
    
    }
    
    ############
    
    class Solution {
        public String countAndSay(int n) {
            String s = "1";
            while (--n > 0) {
                StringBuilder t = new StringBuilder();
                for (int i = 0; i < s.length();) {
                    int j = i;
                    while (j < s.length() && s.charAt(j) == s.charAt(i)) {
                        ++j;
                    }
                    t.append((j - i) + "");
                    t.append(s.charAt(i));
                    i = j;
                }
                s = t.toString();
            }
            return s;
        }
    }
    
  • // OJ: https://leetcode.com/problems/count-and-say/
    // Time: O(N)
    // Space: O(N)
    class Solution {
    public:
        string countAndSay(int n) {
            if (n == 1) return "1";
            string s = countAndSay(n - 1), ans;
            for (int i = 0, N = s.size(); i < N; ++i) {
                char d = s[i];
                int cnt = 1;
                while (i + 1 < N && s[i + 1] == s[i]) ++i, ++cnt;
                ans += to_string(cnt) + d;
            }
            return ans;
        }
    };
    
  • class Solution:
        def countAndSay(self, n: int) -> str:
            s = '1'
            for _ in range(n - 1):
                i = 0
                t = []
                while i < len(s):
                    j = i
                    while j < len(s) and s[j] == s[i]:
                        j += 1
                    t.append(str(j - i))
                    t.append(str(s[i]))
                    i = j
                s = ''.join(t)
            return s
    
    ############
    
    class Solution(object):
      def countAndSay(self, n):
        """
        :type n: int
        :rtype: str
        """
        ans = "1"
        n -= 1
        while n > 0:
          res = ""
          pre = ans[0]
          count = 1
          for i in range(1, len(ans)):
            if pre == ans[i]:
              count += 1
            else:
              res += str(count) + pre
              pre = ans[i]
              count = 1
          res += str(count) + pre
          ans = res
          n -= 1
        return ans
    
    
  • func countAndSay(n int) string {
    	s := "1"
    	for k := 0; k < n-1; k++ {
    		t := &strings.Builder{}
    		i := 0
    		for i < len(s) {
    			j := i
    			for j < len(s) && s[j] == s[i] {
    				j++
    			}
    			t.WriteString(strconv.Itoa(j - i))
    			t.WriteByte(s[i])
    			i = j
    		}
    		s = t.String()
    	}
    	return s
    }
    
  • function countAndSay(n: number): string {
        let s = '1';
        for (let i = 1; i < n; i++) {
            let t = '';
            let cur = s[0];
            let count = 1;
            for (let j = 1; j < s.length; j++) {
                if (s[j] !== cur) {
                    t += `${count}${cur}`;
                    cur = s[j];
                    count = 0;
                }
                count++;
            }
            t += `${count}${cur}`;
            s = t;
        }
        return s;
    }
    
    
  • const countAndSay = function (n) {
        let s = '1';
    
        for (let i = 2; i <= n; i++) {
            let count = 1,
                str = '',
                len = s.length;
    
            for (let j = 0; j < len; j++) {
                if (j < len - 1 && s[j] === s[j + 1]) {
                    count++;
                } else {
                    str += `${count}${s[j]}`;
                    count = 1;
                }
            }
            s = str;
        }
        return s;
    };
    
    
  • using System.Text;
    public class Solution {
        public string CountAndSay(int n) {
            var s = "1";
            while (n > 1)
            {
                var sb = new StringBuilder();
                var lastChar = '1';
                var count = 0;
                foreach (var ch in s)
                {
                    if (count > 0 && lastChar == ch)
                    {
                        ++count;
                    }
                    else
                    {
                        if (count > 0)
                        {
                            sb.Append(count);
                            sb.Append(lastChar);
                        }
                        lastChar = ch;
                        count = 1;
                    }
                }
                if (count > 0)
                {
                    sb.Append(count);
                    sb.Append(lastChar);
                }
                s = sb.ToString();
                --n;
            }
            return s;
        }
    }
    

All Problems

All Solutions