leetcode

// 38. Count and Say
#include "leetcode.h"

/*
 * 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 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. given a positive integer 'n', return the n'th
 * term of the count and say sequence.
 */

char *countAndSay(int n) {
  if (n == 1)
    return "1";
  char *s = countAndSay(n - 1), curr = *s;
  char *ans = (char *)malloc(4463 * sizeof(char));
  int m = strlen(s), idx = 0, cnt = 1;
  for (int i = 1; i < m; i++) {
    char c = *(s + i);
    if (c == curr)
      cnt++;
    else {
      *(ans + idx++) = ('0' + cnt);
      *(ans + idx++) = curr;
      curr = c;
      cnt = 1;
    }
  }
  *(ans + idx++) = ('0' + cnt);
  *(ans + idx++) = curr;
  *(ans + idx) = '\0';
  return ans;
}

int main() {
  char *cas1 = countAndSay(4), *cas2 = countAndSay(1);
  printf("%s\n", cas1); // expect: 1211
  printf("%s\n", cas2); // expect: 1
  free(cas1);
  free(cas2);
}