880. decoded string at index

880. Decoded string at index

Given an encoding string S. Please find out Decoding strings And write it to tape . When decoding , From the encoding string Read one character at a time , And take the following steps ：

 If the characters read are letters , Then write the letter on the tape .
 If the characters read are numbers （ for example  d）, The entire current tape will be rewritten in total  d-1  Time .

Now? , For a given encoding string S And index K, Find and return the... In decoding string K Letters .

Example 1：

Input ：S = “leet2code3”, K = 10
Output ：“o”
explain ：
The decoded string is “leetleetcodeleetleetcodeleetleetcode”.
The... In the string 10 One letter is “o”.

Example 2：

Input ：S = “ha22”, K = 5
Output ：“h”
explain ：
The decoded string is “hahahaha”. The first 5 One letter is “h”.

Example 3：

Input ：S = “a2345678999999999999999”, K = 1
Output ：“a”
explain ：
The decoded string is “a” repeat 8301530446056247680 Time . The first 1 One letter is “a”.

int re;
int kt;

void f(char * s,int end,int epo){
    

    
            while(epo&&kt!=0){
    
                int j=0;
                while(j!=end&&kt!=0){
    
                     if(s[j]>='a'&&s[j]<='z'){
    
                         
                           kt--;
                          //printf("--%c %d ",s[j],kt);
                           if(kt==0){
    
                               s[j+1]='\0';
                                re=j;
                             }
                         }
                         else{
    
                             
                             f(s,j,s[j]-'0'-1);
                         }
                         

                    j++;

                }

                epo--;
            }

      

}

char * decodeAtIndex(char * s, int k){
    
    int i=0;
    kt=k;
    re=0;
  
 
 
     f(s,strlen(s),1);
     return s+re;
    // while(s[i]!='\0'){
    
    
        
    // if(s[i]>='a'&&s[i]<='z'){
    
    // k--;
    // printf("--%c %d",s[i],k);
    // if(k==0){
    
    // s[i+1]='\0';
    // return s+i;
    // }
    // }
    // else{
    
    // int epo=s[i]-'0'-1;
    // int end=i;
    // while(epo){
    
    // int j=0;
    // while(j!=i){
    
    // if(s[j]>='a'&&s[j]<='z'){
    
                         
    // k--;
    // printf("%c %d ",s[j],k,j);
    // if(k==0){
    
    // s[j+1]='\0';
    // return s+j;
    // }
    // }
                         

    // j++;

    // }

    // epo--;
    // }

    // }
    // i++;

// }

return 'a';
}

There is also a powerful algorithm , It's great to start from the back ：

//  Reverse processing 

char * decodeAtIndex(char * S, int K)
{
    
    if (S == NULL || strlen(S) == 0 || K < 1) {
    
        return NULL;
    }

    char* result = (char*)malloc(2 * sizeof(char));
    if (result != NULL) {
    
        memset(result, 0, 2 * sizeof(char));
    }

    int len = strlen(S);
    long strSize = 0;

    // 1.  Calculate the length of the expanded string 
    for (int i = 0; i < len; i++) {
    
        char c = S[i];
        if (isalpha(c)) {
    
            strSize++;
            continue;
        }

        if (isdigit(c)) {
    
            strSize = strSize * (c - '0');
        }
    }

    if (K > strSize) {
    
        return NULL;
    }

    // 2.  From post-processing 
    for (int i = len - 1; i >= 0; i--) {
    
        K = K % strSize;
        if (K == 0 && isalpha(S[i])) {
    
		    result[0] = S[i];
            result[1] = '\0';
            return result;
        }

	    if (isdigit(S[i])) {
    
		    strSize /= S[i] - '0';
        } else {
    
		    strSize--;
        }
    }

    return NULL;
}