3093. Longest Common Suffix Queries

// 演算法：把每個容器字串「反轉後」插入字典樹，後綴比較變成前綴比較。
// Algorithm: insert each container word reversed into a Trie, turning the
// "longest common suffix" comparison into a "longest common prefix" walk.
// 每個節點記錄經過它的最佳容器索引（長度最短、其次索引最小）。
// Each node remembers the best container index passing through it
// (shortest length first, then smallest index). A query reversed then
// walks down as far as possible; the stop node's best index is the answer.

#include <string.h>   // strlen / 取字串長度
#include <stdlib.h>   // malloc, free / 動態記憶體
#include <limits.h>   // INT_MAX / int 的最大值

int* stringIndices(char** wordsContainer, int wordsContainerSize,
                   char** wordsQuery, int wordsQuerySize, int* returnSize) {
    // 先算出所有容器字串的總字元數，用來決定最多需要幾個節點（+1 給根節點）。
    // Count total characters across container words to size the Trie (+1 for root).
    long totalNodes = 1;                                  // 1 = 根節點 / the root
    for (int i = 0; i < wordsContainerSize; i++)
        totalNodes += (long)strlen(wordsContainer[i]);    // 每個字元最多新增一個節點 / each char may add one node

    // children[node][c] = 第 node 個節點、字母 c 方向的子節點編號，-1 表示沒有。
    // children[node][c] = child node id along letter c from `node`; -1 means none.
    // 寫法 int (*children)[26] 代表「指向一個含 26 個 int 的陣列」的指標，
    // i.e. a pointer to arrays-of-26-ints, so children[node] is one node's 26 slots.
    int (*children)[26] = malloc(sizeof(int[26]) * totalNodes);
    int *bestIdx = malloc(sizeof(int) * totalNodes);      // 每節點的最佳索引 / best index per node
    int *bestLen = malloc(sizeof(int) * totalNodes);      // 對應的字串長度 / its word length

    // 初始化根節點（編號 0）。 / Initialise the root (id 0).
    for (int j = 0; j < 26; j++) children[0][j] = -1;     // 26 個方向都還沒有子節點 / no children yet
    bestIdx[0] = -1;                                      // 尚未放入任何字串 / no word stored yet
    bestLen[0] = INT_MAX;                                 // 用最大值，任何真實長度都比它小 / so any real length wins
    int cnt = 1;                                          // 已使用節點數，下一個新節點用此編號 / next free node id

    // ---- 插入每個容器字串（反轉走訪）---- / insert each container word, reversed
    for (int i = 0; i < wordsContainerSize; i++) {
        int len = (int)strlen(wordsContainer[i]);         // 這個字串的長度 / length of this word
        int node = 0;                                     // 從根節點開始 / start at the root

        // 根節點代表「空後綴」，每個字串都會更新它。 / root = empty suffix, every word touches it.
        if (len < bestLen[0]) { bestLen[0] = len; bestIdx[0] = i; }  // 只在更短時覆蓋 → 同長保留較早者 / strict < keeps earliest on ties

        // 從字串「最後一個字元」往前走，等同走訪反轉字串。
        // Walk from the LAST character backwards = traversing the reversed string.
        for (int p = len - 1; p >= 0; p--) {
            int c = wordsContainer[i][p] - 'a';           // 字母轉成 0..25 的索引 / map 'a'..'z' to 0..25
            if (children[node][c] == -1) {                // 這個方向還沒有節點就新建一個 / create child if missing
                children[node][c] = cnt;                  // 記下新節點的編號 / link to the new node id
                for (int j = 0; j < 26; j++) children[cnt][j] = -1;  // 新節點清空子節點 / clear its children
                bestIdx[cnt] = -1;                        // 新節點尚無最佳值 / no best yet
                bestLen[cnt] = INT_MAX;
                cnt++;                                    // 消耗一個節點編號 / consume one node id
            }
            node = children[node][c];                     // 走到子節點 / descend into the child
            // 此節點代表目前已匹配的這段後綴，更新它的最佳索引。
            // This node represents the suffix matched so far; update its best index.
            if (len < bestLen[node]) { bestLen[node] = len; bestIdx[node] = i; }
        }
    }

    // ---- 回答每個查詢 ---- / answer each query
    int *ans = malloc(sizeof(int) * wordsQuerySize);      // 結果陣列 / the output array
    for (int i = 0; i < wordsQuerySize; i++) {
        int len = (int)strlen(wordsQuery[i]);
        int node = 0;                                     // 從根節點開始往下走 / start descending from root
        for (int p = len - 1; p >= 0; p--) {              // 同樣反轉走訪 / reversed walk again
            int c = wordsQuery[i][p] - 'a';
            if (children[node][c] == -1) break;           // 沒有共同後綴可延伸就停 / stop when no shared suffix
            node = children[node][c];                     // 否則繼續往下 / otherwise go deeper
        }
        ans[i] = bestIdx[node];                           // 停下節點的最佳索引就是答案 / best index here is the answer
    }

    *returnSize = wordsQuerySize;                         // 告訴呼叫者結果長度 / report output length
    free(children); free(bestIdx); free(bestLen);         // 釋放 Trie 記憶體，避免洩漏 / free Trie memory
    return ans;                                           // ans 由 LeetCode 接手釋放 / LeetCode frees ans
}

// 演算法與 C 版相同：反轉後插入字典樹，後綴比較變前綴走訪。
// Same algorithm as the C version: reverse words, insert into a Trie, so the
// longest-common-suffix query becomes a longest-common-prefix walk.
// 每個節點存「最佳容器索引」：長度最短優先，長度相同取較早索引。
// Each node stores the best container index: shortest length, ties broken by earliest index.

#include <vector>
#include <string>
#include <array>
#include <climits>
using namespace std;

class Solution {
public:
    vector<int> stringIndices(vector<string>& wordsContainer, vector<string>& wordsQuery) {
        // Trie 節點：26 個子節點（用 array 固定大小）+ 目前最佳索引與其長度。
        // Trie node: 26 children (fixed-size std::array) + the current best index and its length.
        struct Node {
            array<int, 26> children;   // children[c] = 子節點在 vector 中的位置，-1 表示沒有 / child id, -1 = none
            int bestIdx;               // 最佳容器索引 / best container index
            int bestLen;               // 最佳字串長度 / that word's length
            Node() : bestIdx(-1), bestLen(INT_MAX) { children.fill(-1); } // 建構時全部初始化 / init on construction
        };

        // 用 vector<Node> 當作節點池，索引就是節點編號；trie[0] 是根節點。
        // A vector<Node> is our node pool; the index is the node id; trie[0] is the root.
        vector<Node> trie(1);          // 先放一個根節點 / start with just the root

        // ---- 插入每個容器字串 ---- / insert each container word
        for (int i = 0; i < (int)wordsContainer.size(); i++) {
            const string& w = wordsContainer[i];   // const& 避免複製字串 / reference avoids copying the string
            int len = (int)w.size();
            int node = 0;                           // 從根開始 / start at root

            // 根節點對應空後綴，先更新它。 / root = empty suffix; update it first.
            if (len < trie[node].bestLen) { trie[node].bestLen = len; trie[node].bestIdx = i; } // strict < 保留較早者 / keeps earliest on ties

            // 從末尾往前 = 走訪反轉字串。 / iterate from the end = traverse the reversed word.
            for (int p = len - 1; p >= 0; p--) {
                int c = w[p] - 'a';                 // 字母轉 0..25 / map letter to 0..25
                if (trie[node].children[c] == -1) { // 需要新節點 / need to create a child
                    trie[node].children[c] = (int)trie.size();  // 新節點編號 = 目前大小 / new id = current size
                    trie.emplace_back();            // 在尾端就地建構一個 Node / build a Node in place at the back
                    // 注意：emplace_back 可能讓 vector 重新配置記憶體，
                    // 但我們全程用「索引」而非指標/參照存取，所以安全。
                    // Note: emplace_back may reallocate, but we only use indices (not pointers), so it's safe.
                }
                node = trie[node].children[c];      // 走到子節點 / descend
                if (len < trie[node].bestLen) { trie[node].bestLen = len; trie[node].bestIdx = i; } // 更新此後綴節點 / update this suffix node
            }
        }

        // ---- 回答查詢 ---- / answer the queries
        vector<int> ans;
        ans.reserve(wordsQuery.size());            // 預先配置容量，避免多次重新配置 / reserve to avoid reallocations
        for (const string& q : wordsQuery) {       // range-for：逐一取得每個查詢字串 / range-for over queries
            int node = 0;                          // 從根往下 / descend from root
            for (int p = (int)q.size() - 1; p >= 0; p--) {
                int c = q[p] - 'a';
                if (trie[node].children[c] == -1) break; // 無法再延伸共同後綴 / no further shared suffix
                node = trie[node].children[c];     // 繼續往下 / go deeper
            }
            ans.push_back(trie[node].bestIdx);     // 停下節點的最佳索引 / best index at the stop node
        }
        return ans;
    }
};