C++ Fully optimized Trie 99% faster 87% less memory
This is based on the Trie approach but with significantly less memory usage.\nMy original Trie was 779 ms\t700.9 MB\nThis one is 353 ms\t186.5 MB\nhttps://leetc
This is based on the Trie approach but with significantly less memory usage.\nMy original Trie was 779 ms\t700.9 MB\nThis one is 353 ms\t186.5 MB\nhttps://leetcode.com/submissions/detail/824255922/\n\nI don\'t remember what this method is called. Please comment if you know the name.\n\nTake "abcd", "abef" for example:\n1. "abcd": I will first create the "a" node in Trie, then put "abcd" into str field of the "a" node and stop.\n2a. "abef": I see that "a" node exists, and the str field is not empty. Thus I need to move the "abcd".\n2b. For the original "abcd", "b" node is created. I then check if b also exists in "abef" in the same position.\n2c. I continue to go thru the first string until either my current index exceeds the length of either string, or if the character at the current position in both strings no longer matches.\n2d. Finally, for "abcd", I create the "c" node, and copy "cd" into it.\n2e. For "abef", I create the "e" node, and copy "ef" into it.\n2f. I clean up the "abcd" in the "a" node because it has been moevd.\n\n```\nclass Solution {\npublic:\n    typedef struct Trie {\n        struct Trie *data[26]{};\n        char *str{};\n        int vis{}, slen{};\n    } Trie;\n\n    vector<int> sumPrefixScores(vector<string>& words) {\n        vector<int> ret;\n        Trie *root = (Trie *) calloc(1, sizeof(Trie)), *tmp, *tmp2;\n        int sum, depth;\n\n        for (string &x : words)\n        {\n            tmp = root;\n            for (int i = 0, ilen = x.size(); i < ilen; ++i)\n            {\n                char y = x[i] - \'a\';\n                if (!tmp->data[y])\n                {\n                    // If the node does not exist, create node, copy the entire substring into "str" field and stop\n                    tmp->data[y] = (Trie *) calloc(1, sizeof(Trie));\n                    tmp = tmp->data[y];\n                    tmp->vis = 1;\n                    tmp->slen = ilen - i;\n                    tmp->str = (char *) calloc(1, tmp->slen + 1);\n                    memcpy(tmp->str, x.data() + i, tmp->slen);\n                    break;\n                }\n\n                tmp = tmp->data[y];\n                ++tmp->vis;\n                // If the node exists and "str" field is empty, continue\n                if (tmp->slen == 0) continue;\n\n                int j, jlen = tmp->slen;\n                char *&ts = tmp->str;\n                int &tslen = tmp->slen;\n                // Find the index where the two strings are no longer the same\n                for (j = 1; j < jlen && j + i < ilen && x[j + i] == ts[j]; ++j)\n                {\n                    y = ts[j] - \'a\';\n                    tmp->data[y] = (Trie *) calloc(1, sizeof(Trie));\n                    tmp = tmp->data[y];\n                    tmp->vis = 2;\n                }\n\n                // Create new nodes and copy substrings for the two strings, if applicable\n                tmp2 = tmp;\n                if (j < jlen)\n                {\n                    y = ts[j] - \'a\';\n                    tmp->data[y] = (Trie *) calloc(1, sizeof(Trie));\n                    tmp = tmp->data[y];\n                    tmp->vis = 1;\n                    tmp->slen = jlen - j;\n                    tmp->str = (char *) calloc(1, tmp->slen + 1);\n                    memcpy(tmp->str, ts + j, tmp->slen);\n                }\n                j += i;\n                if (j < ilen)\n                {\n                    tmp = tmp2;\n                    y = x[j] - \'a\';\n                    tmp->data[y] = (Trie *) calloc(1, sizeof(Trie));\n                    tmp = tmp->data[y];\n                    tmp->vis = 1;\n                    tmp->slen = ilen - j;\n                    tmp->str = (char *) calloc(1, tmp->slen + 1);\n                    memcpy(tmp->str, x.data() + j, tmp->slen);\n                }\n                free(ts);\n                ts = NULL;\n                tslen = 0;\n                break;\n            }\n        }\n\n        // Tally results\n        for (string &x : words)\n        {\n            tmp = root;\n            sum = depth = 0;\n            for (char y : x)\n            {\n                y -= \'a\';\n                tmp = tmp->data[y];\n                if (tmp->vis == 1)\n                {\n                    sum += x.size() - depth;\n                    break;\n                }\n                sum += tmp->vis;\n                ++depth;\n            }\n            ret.push_back(sum);\n        }\n\n        return ret;\n    }\n};\n```
['C', 'C++']