3043. Find the Length of the Longest Common Prefix

// 演算法：把 arr1 每個元素的「所有前綴」放進手寫雜湊表 S（開放定址 + 線性探測）。
// Algorithm: insert every prefix of every arr1[i] into a hand-rolled open-addressing
// hash table S. Then for each y in arr2, scan y's prefixes from longest to shortest
// (by repeatedly dividing by 10) and record the first hit's digit count.

#include <stdlib.h>   // calloc / free
#include <string.h>   // (not strictly needed but commonly included)

// 計算正整數 x 的位數 / count digits of positive integer x.
static int numDigits(int x) {
    int d = 0;                              // 累計位數 / digit counter
    while (x > 0) {                         // 還有位數沒砍完 / while digits remain
        d++;                                // 位數 +1 / increment count
        x /= 10;                            // 砍掉最右邊一位 / drop rightmost digit
    }
    return d;                               // 回傳位數 / return result
}

int longestCommonPrefix(int* arr1, int arr1Size, int* arr2, int arr2Size) {
    // 雜湊表槽位數選 2^20 ≈ 1,048,576，最多約 4.5×10^5 個鍵，負載因子 < 0.5。
    // Table size 2^20 keeps load factor < 0.5 for up to ~4.5×10^5 keys.
    const unsigned CAP = 1u << 20;          // 容量必須是 2 的次方 / capacity must be power of 2
    const unsigned MASK = CAP - 1;          // 用 & MASK 取餘（比 % 快）/ fast modulo via bitmask

    // calloc 把整塊記憶體歸零；因為題目保證輸入 ≥ 1，我們用 0 代表「空槽」。
    // calloc zeroes the memory; since all input values are ≥ 1, 0 safely means "empty slot".
    int *keys = (int*)calloc(CAP, sizeof(int));

    // -------- Step 1: 把 arr1 所有前綴塞進雜湊表 / insert all prefixes from arr1 --------
    for (int i = 0; i < arr1Size; i++) {    // 走訪 arr1 每個元素 / iterate arr1
        int x = arr1[i];                    // 取目前的數 / current value
        while (x > 0) {                     // 一直砍到變 0 / generate all prefixes
            // 用 Knuth's multiplicative hash：把 int 乘上一個質數常數，再取低位作為 index。
            // Knuth multiplicative hash: multiply by a large prime-ish constant and mask.
            unsigned h = ((unsigned)x * 2654435761u) & MASK;

            // 線性探測：若該槽已被別的 key 佔住，就往後一格找。
            // Linear probing: if occupied by a different key, step forward.
            while (keys[h] != 0 && keys[h] != x) {
                h = (h + 1) & MASK;          // 環狀往後 / wrap-around forward step
            }
            keys[h] = x;                    // 找到空槽或本身已存在，寫入即可 / write (idempotent)
            x /= 10;                        // 砍掉最右一位，產生下一個前綴 / next shorter prefix
        }
    }

    // -------- Step 2: 對 arr2 每個 y 找最長能命中 S 的前綴 / probe arr2 ---------------
    int best = 0;                           // 目前最佳答案 / best length so far
    for (int j = 0; j < arr2Size; j++) {    // 走訪 arr2 每個元素 / iterate arr2
        int y = arr2[j];                    // 從完整的 y 開始 / start from full y
        while (y > 0) {                     // 嘗試所有前綴（由長到短）/ longest → shortest
            unsigned h = ((unsigned)y * 2654435761u) & MASK;  // 同樣的雜湊函式 / same hash
            int found = 0;                  // 旗標：是否找到 / found flag
            while (keys[h] != 0) {          // 探測直到遇到空槽 / probe until empty
                if (keys[h] == y) { found = 1; break; }       // 命中！/ hit
                h = (h + 1) & MASK;          // 否則繼續往後 / otherwise keep probing
            }
            if (found) {                    // 第一次命中就是最長前綴 / first hit = longest
                int d = numDigits(y);       // 位數即答案候選 / digit count is the candidate
                if (d > best) best = d;     // 更新全域最佳 / update best
                break;                      // 不必再砍 y / done with this y
            }
            y /= 10;                        // 沒命中，砍一位再試 / try shorter prefix
        }
    }

    free(keys);                             // 釋放雜湊表記憶體 / release the table
    return best;                            // 回傳答案 / return result
}

// 演算法：和 C 版完全一樣，差別只在用 std::unordered_set 取代手寫雜湊表。
// Algorithm: identical to the C version, but using std::unordered_set instead of a
// hand-rolled hash table. Insert every prefix from arr1, then for each y in arr2 walk
// its prefixes from longest to shortest and stop at the first one present in the set.

#include <vector>
#include <unordered_set>
using namespace std;

class Solution {
public:
    int longestCommonPrefix(vector<int>& arr1, vector<int>& arr2) {
        // unordered_set<int>：STL 提供的雜湊集合；insert / count 平均 O(1)。
        // unordered_set<int>: STL hash set with average O(1) insert and lookup.
        unordered_set<int> prefixes;

        // reserve 預先配置桶數，避免插入過程中反覆 rehash，加速約 1.5–2x。
        // Pre-reserve buckets so we don't rehash repeatedly while inserting.
        prefixes.reserve(arr1.size() * 9);

        // range-for + 值複製：x 是 arr1 元素的副本，可以安全修改不影響原陣列。
        // Range-for with a value copy: x is a local copy, safe to mutate.
        for (int x : arr1) {
            while (x > 0) {                  // 枚舉 x 的所有前綴 / enumerate prefixes
                prefixes.insert(x);          // 插入雜湊集合（重複插入不影響）/ idempotent insert
                x /= 10;                     // 砍掉最右一位 / drop rightmost digit
            }
        }

        int best = 0;                        // 目前最佳長度 / best length so far
        for (int y : arr2) {                 // 對 arr2 每個 y / for each y in arr2
            while (y > 0) {                  // 由長到短嘗試 y 的前綴 / longest → shortest
                // count(y) 回傳 0 或 1，表示 y 是否在集合中。
                // count(y) returns 0 or 1, indicating membership.
                if (prefixes.count(y)) {
                    int d = 0;               // 計算 y 的位數 / count digits of y
                    for (int t = y; t > 0; t /= 10) d++;  // 經典數位計數迴圈 / classic loop
                    best = max(best, d);     // 更新最佳 / update best
                    break;                   // 第一次命中即最長 / first hit is longest
                }
                y /= 10;                     // 沒命中，再砍一位 / shorten and retry
            }
        }
        return best;                         // 回傳答案 / return answer
    }
};