LeetCode 3043. Find the Length of the Longest Common Prefix

 

문제

두 정수 배열 $arr1, arr2$가 있다.

$1 \le i \le |arr1|, 1 \le j \le |arr2|$인 $i, j$에 대해,
$arr1_i$와 $arr2_j$의 Longest Common Prefix 중 가장 큰 값을 구해보자.

풀이

두 배열의 크기 제한이 모두 $50,000$이기 때문에, 완전 탐색을 하면 시간 초과가 날 것 같다.

배열의 원소를 정수가 아니라 문자열로 본다면, 문자열 집합에서 특정 문자열을 검색하는 문제로 바꿀 수 있다.
문자열 집합에서 검색을 지원하는 자료 구조인 트라이를 사용해보자.

$arr1$의 모든 원소를 트라이에 삽입해놓고, $arr2$의 원소를 하나씩 트라이에서 검색한다.
검색할 때는, 검색 문자열과 일치하는 최대 깊이까지 내려가면 된다.

코드

class TrieNode {
    TrieNode[] next;
    TrieNode() {
        next = new TrieNode[10];
    }
}

class Trie {
    TrieNode root;
    Trie() {
        root = new TrieNode();
    }

    void insert(int x) {
        TrieNode cur = root;
        for(char c : Integer.toString(x).toCharArray()) {
            int n = c - '0';
            if(cur.next[n] == null) {
                cur.next[n] = new TrieNode();
            }
            cur = cur.next[n];
        }
    }

    int find(int x) {
        TrieNode cur = root;
        int ret = 0;
        for(char c : Integer.toString(x).toCharArray()) {
            int n = c - '0';
            if(cur.next[n] == null) break;
            cur = cur.next[n];
            ret++;
        }
        return ret;
    }
}

class Solution {
    public Trie trie;

    public int longestCommonPrefix(int[] arr1, int[] arr2) {
        trie = new Trie();
        for(int x : arr1) trie.insert(x);

        int answer = 0;
        for(int x : arr2) answer = Math.max(answer, trie.find(x));

        return answer;
    }
}