//递归
char * countAndSay(int n){
    char *say = (char*)malloc(sizeof(char)*5000);
    
    if (n>30||n<1)
        return NULL;
    
    if (n == 1){
        free(say);
        return "1";
    }
    else{
        char *s = countAndSay(n-1);
        int pcounts=0, pnumber=1;
        for(int i=0;s[i]!=‘\0‘;i++){
            if (i==0){
                say[pnumber]=s[i];
                say[pcounts]=‘1‘;
            }
            else if (s[i-1]==s[i]){
                say[pcounts]++;
            }
            else{
                pnumber+=2;
                pcounts+=2;
                say[pcounts]=‘1‘;
                say[pnumber]=s[i];
            }
        }
        say[pnumber+1]=‘\0‘;
        return &say[0];
    }
}

//双指针
//https://leetcode-cn.com/problems/count-and-say/solution/38-wai-guan-shu-lie-shuang-zhi-zhen-by-yiluolion/
char * countAndSay(int n){    
    if (n>30||n<1)
        return NULL;

    char *cur = (char*)malloc(sizeof(char)*5000);
    char *pre = (char*)malloc(sizeof(char)*5000);
    int p, i, start, end;

    cur[0]=‘1‘;
    cur[1]=‘\0‘;
    i=1;
    while (i<n){
        strcpy(pre, cur); //why have to use strcpy(pre, cur)? and cannot be pre=cur?
        *cur="";
        p=0;
        start=0;
        end=0;
        while(pre[end]!=‘\0‘){
            while (pre[end]!=‘\0‘&&pre[start]==pre[end])
                end++;
            cur[p++]=end-start+‘0‘;
            cur[p++]=pre[start];
            start=end;
        } 
        cur[p]=‘\0‘;  
        i++;
    }
    return cur;
}