3043. Find the Length of the Longest Common Prefix

Problem : https://leetcode.com/problems/find-the-length-of-the-longest-common-prefix

 

Difficulty : Medium

 

Status : Solved

 

Time : 00:18:42

 

---

 

문제 설명

 

 

양의 정수로 구성된 arr1, arr2가 주어진다.

 

양의 정수의 접두사는 제일 왼쪽부터 시작하는 하나 이상의 숫자로 구성된 정수를 의미한다. 예를 들어, 12345에서 123은 접두사이지만 234는 접두사가 아니다.

 

a, b의 공통 접두사가 c라면, c는 a와 b 양 쪽 모두 접두사이다. 예를 들어서, 5655359와 53554는 공통 접두사로 565를 가지지만 1223과 43456은 공통 접두사를 가지지 않는다.

 

arr1에 속하는 정수 x와, arr2에 속하는 정수 y의 모든 조합 (x, y)에 대해, 가장 긴 공통 접두사의 길이를 구해야 한다.

 

모든 조합에 대한 가장 긴 공통 접두사의 길이를 반환하라. 만약 그러한 공통접두사가 없다면, 0을 반환하라. 

---

 

풀이

 

첫 번째 시도 : 트라이.

 

트라이 자료구조는 접두사 검사와 같은 케이스에 효율적이다. arr1로 트라이를 생성하고, arr2의 모든 숫자들로 트라이를 검사한다. 트라이에서 더 이상 방문할 수 없을때(즉 트라이 내에 i번째 숫자가 없을때) 탐색을 종료한다. 종료 시점의 깊이가 arr2의 해당 숫자 - arr1 조합에서의 가장 긴 공통 접두사 길이이다.

 

풀이 코드 (Trie)

class Trie:
    def __init__(self) :
        self.children = dict()
    def isin(self, num: str) -> bool :
        return num in self.children
    def getChild(self, num: str) :
        return self.children[num]
    def makeChild(self, num: str) :
        self.children[num] = Trie()

class Solution:
    def makeTrie(self, num: int):
        cur = self.trie
        for n in str(num) :
            if not cur.isin(n) :
                cur.makeChild(n)
            cur = cur.getChild(n)

    def findPrefix(self, num: int) -> int:
        cur = self.trie
        for i, n in enumerate(str(num)) :
            if not cur.isin(n) :
                return i
            cur = cur.getChild(n)
        return i+1

    def longestCommonPrefix(self, arr1: List[int], arr2: List[int]) -> int:
        self.trie = Trie()
        for n in arr1 :
            self.makeTrie(n)
        result = 0
        for n in arr2 :
            result = max(result, self.findPrefix(n))
        return result

 

 

다른 방식 해쉬 - 즉 hashset을 생각해보자.

 

우리는 arr1의 모든 원소에 대해 가능한 모든 경우의 접두사를 구할 수 있다. 운이 좋게도, 모든 원소는 숫자로 구성되어 있으며, 숫자가 최장 10^8이라는 점이다. 즉 접두사의 최대 경우의 수는 한정되어 있다. 접두사를 모두 해쉬에 저장하고, arr2의 각 숫자에 대해 접두사를 해쉬에 대입해보자.

 

트라이, 해쉬 모두 시간복잡도는 동일하다(생성, 탐색에 arr의 원소의 개수 x 숫자의 길이만큼이 소요된다).

 

풀이 코드 (set)

class Solution:
    def longestCommonPrefix(self, arr1: List[int], arr2: List[int]) -> int:
        prefix = set()
        result = 0

        for num in arr1 :
            tmp = ''
            for n in str(num) :
                tmp += n
                prefix.add(tmp)

        for num in arr2 :
            tmp = ''
            for n in str(num) :
                if tmp + n not in prefix :
                    break
                tmp += n
            result = max(result, len(tmp))
        return result