(C++, Python3) - LeetCode (easy) 3043. Find the Length of the Longest Common Prefix

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

 

Trie 자료구조로 해결한 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

조회에 최적화된 hash 기반 자료구조인 c++엔 unordered_map, python에서는 dictionary를 이용해 trie구조를 생성해줍니다.

1. class TrieNode를 선언합니다.

  1-1. 하나의 trie node는 member변수 두개(dict인 children과 boolean isEndOfWord)를 가지고 있습니다.

2. class Trie를 선언합니다. 

  2-1. member변수 root를 선언해 생성자에 TrieNode instance를 생성한 결과값을 저장합니다. 

  2-2. member insert함수를 선언해줍니다. 한 단어에 대한 for loop를 수행하며 다음 각 낱말을 TreeNode에 저장하며 children에 다음 낱말 정보를 저장해줍니다. 

  2-3. member 함수 findCommonPrefixLength를 선언해줍니다. 한 단어에 대한 for loop를 수행하며 해당 tree의 한 줄기를 따라가며 공통된 접두사 길이를 세준 후 반환합니다.

📔 풀이과정

1. 변수 trie를 선언해 Trie instance를 생성한 값을 저장합니다.

2. arr2의 원소를 순회하며 trie자료구조를 각 원소에 대해 생성해줍니다.

3. arr1의 원소를 순회하며 각 원소에서 공통 접두사 길이를 구해 longestCommonLength값을 갱신합니다.

 

📃 예시

arr1 = [323, 322, 132], arr2 = [32] 인 경우

 

arr1의 모든 원소를 insert한 Trie 자료구조

arr2의 32에 대해 findCommonPrefixLength를 수행하며 공통 접두사 길이를 구하게 되면 trie 자료구조에서 '3', '2'를 children을 타고 내려가며 찾게되며 2를 반환하게 됩니다. children에서 각 문자를 찾는 시간은 hash 기반 자료구조이므로 각 O(1)의 평균 소요시간을 가지게 됩니다. 따라서 arr1의 모든 원소(n) * 공통 접두사를 찾는시간(1 ~ logn)만큼의 시간 복잡도를 가지므로 효율성을 통과할 수 있습니다.

📔 정답 출력 | 반환

logestCommonLength를 반환합니다.

---

📕 Code

📔 C++

class TrieNode {
public:
    unordered_map<char, TrieNode*> children;
    bool isEndOfWord;
    
    TrieNode() {
        isEndOfWord = false;
    }
};

class Trie {
private:
    TrieNode* root;

public:
    Trie() {
        root = new TrieNode();
    }

    void insert(const string& word) {
        TrieNode* node = root;
        for (char ch : word) {
            if (node->children.find(ch) == node->children.end()) {
                node->children[ch] = new TrieNode();
            }
            node = node->children[ch];
        }
        node->isEndOfWord = true;
    }

    int findCommonPrefixLength(const string& word) {
        TrieNode* node = root;
        int prefixLen = 0;
        for (char ch : word) {
            if (node->children.find(ch) == node->children.end()) {
                break;
            }
            node = node->children[ch];
            prefixLen++;
        }
        return prefixLen;
    }
};

class Solution {
public:
    int longestCommonPrefix(const vector<int>& arr1, const vector<int>& arr2) {
        Trie trie;
        for (int num : arr2) {
            trie.insert(to_string(num));
        }

        int longestCommonLength = 0;

        for (int num : arr1) {
            string numStr = to_string(num);
            int commonPrefixLength = trie.findCommonPrefixLength(numStr);
            longestCommonLength = max(longestCommonLength, commonPrefixLength);
        }

        return longestCommonLength;
    }
};

 

📔 Python

class TrieNode:
    def __init__(self):
        self.children = {}
        self.isEndOfWord = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.isEndOfWord = True

    def findCommonPrefixLength(self, word):
        node = self.root
        prefixLen = 0
        for char in word:
            if char not in node.children:
                break
            node = node.children[char]
            prefixLen += 1
        return prefixLen
    
class Solution(object):
    def longestCommonPrefix(self, arr1, arr2):
        trie = Trie()
        for num in arr2:
            trie.insert(str(num))

        longestCommonLength = 0
        
        for num in arr1:
            numStr = str(num)
            commonPrefixLength = trie.findCommonPrefixLength(numStr)
            longestCommonLength = max(longestCommonLength, commonPrefixLength)

        return longestCommonLength

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.