50171. Split a string

I'm a slow walker, but I never walk backwards.

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]);
    for(int i=0; i<numPtrArray; i++) free(ptr[i]);
    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)


Sample Output 1 (for the test main.c)

de k
f ij

Sample Input 2 (for the test main.c)


Sample Output 2 (for the test main.c)

jwgt o
lwg kj
it bis
m qrje

Sample Input 3 (for the test main.c)


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