50171. Split a string

Task Description

We want to split a string into tokens and map the address of each token to $n$ character pointer arrays.

We will be given a pointer ptr, which points to an array of $n$ pointers $A$ that ends with NULL. Each element of this pointer array $A$ points to another pointer array $A_1$, $A_2$, ... $A_n$, whose elements point to different tokens within a given string str. The string str contains lowercase alphabets and the delimiter *.

First we split string str with the delimiter * into tokens with strtok, so that every token ends with a '\0'. Then we assign the address of all tokens, in the order they appear in str and one at a time, to the $A_i$ having the minimum total number of characters. If there are more than one $A_i$ having the minimum total number of characters, we choose the one with the smallest index. Finally we end every $A_i$ with a NULL.

The pointer arrays are linked as shown in the following animation when str is abc*de**f*gh***ij*k, and there are four pointer arrays.

The prototype of the function splitAndMap is given by splitAndMap.h as follows.

void splitAndMap(char*** ptr, char* str);

You can use the following main.c to test your function.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "splitAndMap.h"
#define numPtrArray 4
#define MAXLEN 400000
int main(){
    char*** ptr = malloc((numPtrArray+1) * sizeof(char**));
    for(int i=0; i<numPtrArray; i++){
        ptr[i] = malloc(MAXLEN * sizeof(char**));
    }
    ptr[numPtrArray] = NULL;
 
    char str[MAXLEN];
    scanf("%s", str);
 
    splitAndMap(ptr, str);
 
    for(int i=0; i<numPtrArray; i++){
        for(int j=0; ptr[i][j]!=NULL; j++)
            printf("%s ", ptr[i][j]);
        printf("\n");
    }
 
    for(int i=0; i<numPtrArray; i++) free(ptr[i]);
    free(ptr);
    return 0;
}

Note that the number of pointer arrays ($n$) is from 1 to 10. Also you should not use too much memory or you will get MLE.

Input Format (for the test main.c)

The input is a string that contains lowercase alphabets and the delimiter *. The length of the string is between 1 and 400000.

Output Format (for the test main.c)

The outputs are the tokens in all pointer arrays, in increasing index order, and within a pointer array the token will appear in the order is they are added into the pointer array.

Sample Input 1 (for the test main.c)

abc*de**f*gh***ij*k

Sample Output 1 (for the test main.c)

abc
de k
f ij
gh

Sample Input 2 (for the test main.c)

jwgt*lwg*it*m*qrje*bis*kj*o

Sample Output 2 (for the test main.c)

jwgt o
lwg kj
it bis
m qrje

Sample Input 3 (for the test main.c)

a*aa**aa*a*bb*bb******bb*bb*aa*aa*aa**aa*bb*bb*****bb*bb*aa*aa*a*a

Sample Output 3 (for the test main.c)

a bb aa bb aa
aa bb aa bb a
aa bb aa bb a
a bb aa bb aa