題目

3043. Find the Length of the Longest Common Prefix
難度: 中等偏易

題意

給定兩整數陣列arr1與arr2。
找arr1與arr2之間所有整數對中，最長的相同前綴長度。
整數對: 一整數在arr1之中，另一整數arr2之中。
最長相同前綴: 將兩整數對以十進位字串表示時，相同的前綴。

範例1:
Input: arr1 = [1,10,100], arr2 = [1000]
Output: 3
整數對為100與1000，相同的前綴為100，其長度為3。

思路

需要反覆查找某東西在不在? 或某東西有幾個? 馬上聯想到用哈希表。

1. 將其中一個整數陣列的所有前綴造出來，作為哈希表的鍵值。
2. 將另一個整數陣列的所有前綴造出來，檢查哈希表中存不存在。若存在則更新最大的前綴長。

實作

因為只要查存不存在，無須知道前綴的排序，也無須知道前綴有幾個；所以選用unordered_set

class Solution
{
public:
    int longestCommonPrefix(vector<int> &arr1, vector<int> &arr2)
    {
        // prefix integer
        unordered_set<int> us;

        // Build hash map for all prefixes in arr1
        for (auto num : arr1)
        {
            while (num)
            {
                us.insert(num);
                num /= 10;
            }
        }

        // Store the result for max length, so initialize to 0
        int res = 0;

        // Traverse all prefixes in arr2
        for (auto num : arr2)
        {
            while (num)
            {
                if (us.find(num) != us.end())
                {
                    res = max(res, (int)to_string(num).size());
                    // Early return since we only need the longest prefix
                    break;
                }
                num /= 10;
            }
        }

        return res;
    }
};

分析

若兩陣列的大小分別為M, N
時間複雜度: O(M + N)，建表M * O(1)，查表N * O(1)。
空間複雜度: O(max(M, N))，哈希表所需空間。

結果

Accepted
718/718 cases passed (269 ms)
Your runtime beats 67.25 % of cpp submissions
Your memory usage beats 89.16 % of cpp submissions (135.5 MB)

總結

這題是今年2月時的週賽題目，題目不會太難，很貼近實戰。
可惜當時的週賽，還刷得不夠多，哈希表不會用，只拿到TLE。
如今這題已經變反射題，可見菜就多練的重要性...