[LeetCode] 3043. Find the Length of the Longest Common Prefix

https://leetcode.com/problems/find-the-length-of-the-longest-common-prefix/description/?envType=daily-question&envId=2024-09-24

leetcode - Find the Length of the Longest Common Prefix

문제 유형 : 트라이(Trie), 문자열 처리, 해시

문제 난이도 : Medium

 

문제

You are given two arrays with positive integers arr1 and arr2.

A prefix of a positive integer is an integer formed by one or more of its digits, starting from its leftmost digit. For example, 123 is a prefix of the integer 12345, while 234 is not.

A common prefix of two integers a and b is an integer c, such that c is a prefix of both a and b. For example, 5655359 and 56554 have a common prefix 565 while 1223 and 43456 do not have a common prefix.

You need to find the length of the longest common prefix between all pairs of integers (x, y) such that x belongs to arr1 and y belongs to arr2.

Return the length of the longest common prefix among all pairs. If no common prefix exists among them, return 0.

 

두 개의 양의 정수 배열 arr1과 arr2가 주어진다.

두 정수 배열 에서 각각 하나씩 수를 꺼내서 얻을 수 있는 가장 큰 공통 접두사의 길이를 구하시오.

 

풀이

방법 1 - 해시 테이블을 이용한 풀이

한 배열을 이용하여 map[prefix] = true or false로, 미리 접두사 테이블을 만들어놓고,

다른 배열에 있는 수들도 각각 접두사로 만들어서 비교해보면서 값을 비교하면 된다.

존재하는 접두사라면, 그 접두사의 자릿수를 구해서 최대 값을 업데이트하는데 쓸 수 있다.

 

방법 2 - 트라이(Trie)를 이용한 풀이

트라이(Trie)를 만들어서 가장 긴 길이를 얻어낼 수 있다.

 

코드

C++

1 - 해시 테이블을 이용한 풀이

#pragma GCC optimize("03", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    int longestCommonPrefix(vector<int>& arr1, vector<int>& arr2) {
        unordered_map<int, bool> prefixes;
        for(int num : arr2) {
            while(num > 0) {
                prefixes[num] = true;
                num /= 10;
            }
        }
        
        int ans = 0;
        for(auto &num : arr1) {
            while(num > 0) {
                if(prefixes[num]) {
                    ans = max(ans, (int)log10(num) + 1);
                    break;
                }
                num /= 10;
            }
        }

        return ans;
    }
};

 

2 - 트라이를 이용한 풀이

class TrieNode {
public:
    int data;
    bool isTerminal;
    TrieNode* children[10];

    TrieNode(int ch) {
        data = ch;
        isTerminal = false;
        for(int i = 0; i < 10; ++i) {
            children[i] = NULL;
        }
    }
};

class Trie {
    TrieNode* root;
public:
    Trie() {
        root = new TrieNode(-1);
    }

    void insert(int data) {
        auto node = root;

        int divisor = 1;
        while (data / divisor >= 10) {
            divisor *= 10;
        }

        while (divisor > 0) {
            int digit = (data / divisor) % 10;
            if (node->children[digit] == NULL) {
                node->children[digit] = new TrieNode(digit);
            }
            node = node->children[digit];
            divisor /= 10;
        }
        node->isTerminal = true;
    }

    int prefixLen(int data) {
        auto node = root;
        int len = 0;
        int divisor = 1;
        while (data / divisor >= 10) {
            divisor *= 10;
        }

        while (divisor > 0) {
            int digit = (data / divisor) % 10;
            if (node->children[digit] == nullptr) {
                return len;
            } else {
                len++;
                node = node->children[digit];
                divisor /= 10;
            }
        }

        return len;
    }
};

class Solution {
public:
    int longestCommonPrefix(vector<int>& arr1, vector<int>& arr2) {
        Trie* t = new Trie();
        for(int num : arr2) {
            t -> insert(num);
        }

        int ans = 0;
        for(int num : arr1) {
            ans = max(ans, t -> prefixLen(num));
        }

        return ans;
    }
};