link ：https://leetcode.cn/problems/prefix-and-suffix-search/solution/c-by-xun-ge-v-old2/
source ： Power button （LeetCode）

subject

Example

Ideas

Prefix tree
Optimize retrieval using dictionary tree , Use two separately Trie Trees to record w[i] Pre suffix of , That is, it is being saved to left in , Save to right in .
At the same time, for each node of the dictionary tree , We use arrays inode Record the string passing through this node ** w[i]** Where words Subscript in i, If the index array of a dictionary tree node inode by [a1,a2,a3...] It means that the string corresponding to the node is the subscript in the dictionary ** words[a1]、words[a2]、words[a3]...** The prefix of .
So we can suffix before scanning a and b when , Get the corresponding candidate subscript list l1 and l2, Because we will w[i] Add to two t Middle is according to the subscript 「 From small to large 」 Conduct , So we use 「 Double pointer 」 The algorithm starts from l1 and l2 After the end, find the first common element is the answer （ The maximum subscript that satisfies the condition ）.
But after repeated practice, it always times out , Are many people like me , At a loss , I've been struggling for a long time , Finally, I used the idea after sleeping
The main reason is malloc Space above , Because each node needs to open a large space , It takes too much time here
terms of settlement : Replace the array space with a linked list , I'll open a linked list node with a subscript , In this way, the time consumption will be much smaller
Linked list nodes can use head interpolation , Keep the maximum ahead , In this way, the final retrieval can reduce the time
Facts have proved that using linked lists instead of arrays is a very good and feasible idea

Code

Array not optimized

//false  not finished , true  end 
typedef struct Trie{
    int * node;
    int wSize;
    bool logo;
    struct Trie * next[26];
} Trie;
typedef struct WordFilter{
    Trie * left;
    Trie * right;
} WordFilter;

Trie * init_obj(int wordsSize)
{
    Trie * obj = malloc(sizeof(Trie));
    obj->node = (int *)malloc(sizeof(int) * wordsSize);
    memset(obj->node, 0, sizeof(int) * wordsSize);
    for(int i = 0; i < 26; i++)
    {
        obj->next[i] = NULL;
    }
    obj->wSize = wordsSize;
    obj->logo = false;
    return obj;
}
void init_Tair_prefix(Trie * obj, char * word, int inode, int wordsSize)
{
    int len = strlen(word);
    for(int i = 0; i < len; i++)
    {
        if(obj->next[word[i] - 'a'] == NULL)
        {
            Trie * n = init_obj(wordsSize);
            obj->next[word[i] - 'a'] = n;
        }
        obj->node[inode] = len;
        obj = obj->next[word[i] - 'a'];
    }
    obj->node[inode] = len;
    obj->logo = true;
    return;
}
void init_Tair_suff(Trie * obj, char * word, int inode, int wordsSize)
{
    int len = strlen(word);
    for(int i = len-1; i >= 0; i--)
    {
        if(obj->next[word[i] - 'a'] == NULL)
        {
            Trie * n = init_obj(wordsSize);
            obj->next[word[i] - 'a'] = n;
        }
        obj->node[inode] = len;
        obj = obj->next[word[i] - 'a'];
    }
    obj->node[inode] = len;
    obj->logo = true;
    return;
}
WordFilter* wordFilterCreate(char ** words, int wordsSize) {
    WordFilter * obj = malloc(sizeof(WordFilter));
    obj->left = init_obj(wordsSize);
    obj->right = init_obj(wordsSize);
    for(int i = 0; i < wordsSize; i++)
    {
        init_Tair_prefix(obj->left, words[i], i, wordsSize);
        init_Tair_suff(obj->right, words[i], i, wordsSize);
    }
    return obj;
}
#define MAX(a , b) ((a) > (b) ? (a) : (b))
int wordFilterF(WordFilter* obj, char * pref, char * suff) {
    int p_len = strlen(pref);
    int s_len = strlen(suff);
    Trie * l;
    Trie * r;
    l = obj->left;
    r = obj->right;
    for(int i = 0; i < p_len; i++)
    {
        if(l->next[pref[i] - 'a'] == NULL)
        {
            return -1;
        }
        l = l->next[pref[i] - 'a'];
    }
    for(int i = s_len - 1; i >= 0; i--)
    {
        if(r->next[suff[i] - 'a'] == NULL)
        {
            return -1;
        }
        r = r->next[suff[i] - 'a'];
    }
    for(int i = l->wSize - 1; i >= 0 ; i--)
    {
        if(l->node[i] > 0 && r->node[i] > 0)
        {
            return i;
        }
    }
    return -1;
}
void trieFree(Trie * obj)
{
    for(int i = 0; i < 26; i++)
    {
        if(obj->next[i])
        {
            trieFree(obj->next[i]);
        }
    }
    free(obj->node);
    free(obj);
    return;
}
void wordFilterFree(WordFilter* obj) {
    // trieFree(obj->left);
    // trieFree(obj->right);
    free(obj);
    return;
}

/**
 * Your WordFilter struct will be instantiated and called as such:
 * WordFilter* obj = wordFilterCreate(words, wordsSize);
 * int param_1 = wordFilterF(obj, pref, suff);
 
 * wordFilterFree(obj);
*/

List instead of array  

// Linked list 
typedef struct List{
    int node;
    struct List * next;
}List;
// Prefix tree nodes 
//false  not finished , true  end 
typedef struct Trie{
    List * lower;
    struct Trie * next[26];
} Trie;
// Prefix tree head 
typedef struct WordFilter{
    Trie * left;
    Trie * right;
} WordFilter;
// Initialize prefix tree node 
Trie * init_obj()
{
    Trie * obj = malloc(sizeof(Trie));
    obj->lower = malloc(sizeof(List));
    for(int i = 0; i < 26; i++)
    {
        obj->next[i] = NULL;
    }
    return obj;
}
// Add a string to the prefix tree 
void init_Tair_prefix(Trie * obj, char * word, int inode, int len)
{
    for(int i = 0; i < len; i++)
    {
        if(obj->next[word[i] - 'a'] == NULL)
        {
            Trie * n = init_obj();
            n->lower->node = inode;
            n->lower->next = NULL;
            obj->next[word[i] - 'a'] = n;
            obj = obj->next[word[i] - 'a'];
        }
        else
        {
            obj = obj->next[word[i] - 'a'];
            List * m = malloc(sizeof(List));// It already exists , Just add a linked list node , Record the subscript 
            m->node = inode;
            m->next = obj->lower;
            obj->lower = m;
        }
    }
    return;
}
// Add a string to the suffix tree 
void init_Tair_suff(Trie * obj, char * word, int inode, int len)
{
    for(int i = len-1; i >= 0; i--)
    {
        if(obj->next[word[i] - 'a'] == NULL)
        {
            Trie * n = init_obj();
            n->lower->node = inode;
            n->lower->next = NULL;
            obj->next[word[i] - 'a'] = n;
            obj = obj->next[word[i] - 'a'];
        }
        else
        {
            obj = obj->next[word[i] - 'a'];
            List * m = malloc(sizeof(List));
            m->node = inode;
            m->next = obj->lower;
            obj->lower = m;
        }
    }
    return;
}
// Initialize the entire prefix tree , And add all strings 
WordFilter* wordFilterCreate(char ** words, int wordsSize) {
    WordFilter * obj = malloc(sizeof(WordFilter));
    obj->left = init_obj();
    obj->right = init_obj();
    for(int i = 0; i < wordsSize; i++)
    {
        int len = strlen(words[i]);
        init_Tair_prefix(obj->left, words[i], i, len);
        init_Tair_suff(obj->right, words[i], i, len);
    }
    return obj;
}
// Find prefix string and suffix string 
int wordFilterF(WordFilter* obj, char * pref, char * suff) {
    int p_len = strlen(pref);
    int s_len = strlen(suff);
    Trie * l;
    Trie * r;
    l = obj->left;
    r = obj->right;
    for(int i = 0; i < p_len; i++)// Find prefix string 
    {
        if(l->next[pref[i] - 'a'] == NULL)
        {
            return -1;// There is no current prefix , Go straight back to 
        }
        l = l->next[pref[i] - 'a'];
    }
    for(int i = s_len - 1; i >= 0; i--)// Find suffix string , The principle of same 
    {
        if(r->next[suff[i] - 'a'] == NULL)
        {
            return -1;
        }
        r = r->next[suff[i] - 'a'];
    }
    List * m = l->lower;
    List * n = r->lower;
    while(m && n)// Found destination Prefix suffix , Find the largest identical subscript , Because the linked list uses header search , So the maximum value is in front 
    {
        if(m->node == n->node)
        {
            return m->node;
        }
        else if(m->node > n->node)
        {
            m = m->next;
        }   
        else
        {
            n = n->next;
        }
    }
    return -1;
}
void trieFree(Trie * obj)
{
    for(int i = 0; i < 26; i++)
    {
        if(obj->next[i])
        {
            trieFree(obj->next[i]);
        }
    }
    obj->lower->next == NULL;
    free(obj->lower);
    free(obj);
    return;
}
void wordFilterFree(WordFilter* obj) {
    trieFree(obj->left);
    trieFree(obj->right);
    free(obj);
    return;
}

/**
 * Your WordFilter struct will be instantiated and called as such:
 * WordFilter* obj = wordFilterCreate(words, wordsSize);
 * int param_1 = wordFilterF(obj, pref, suff);
 
 * wordFilterFree(obj);
*/

Time and space complexity