[알고리즘] 15번째 문제

[SongGwanSeok]

📝 Description

무엇을?

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

왜?

• (ex 사용자를 인증하기 위해)

❗️Todo

• [ ]
• [ ]
• [ ]

ETC

기타사항

[SongGwanSeok]

https://leetcode.com/problems/sum-of-prefix-scores-of-strings/description/?envType=daily-question&envId=2024-09-25 시간초과

class Solution {
public:
    vector<int> sumPrefixScores(vector<string>& words) {
        int len = words.size();
        vector<int> result(len, 0);

        map<string, int> msi;

        for (int i = 0; i < len; ++i) {
            string tmpS = "";
            for (int j = 0; j < words[i].size(); ++j) {
                tmpS += words[i][j];
                msi[tmpS]++;
            }
        }

        for (int i = 0; i < len; ++i) {
            string tmpS = "";
            for (int j = 0; j < words[i].size(); ++j) {
                tmpS += words[i][j];
                result[i] += msi[tmpS];
            }
        }

        return result;
    }
};

[SongGwanSeok]

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

class Solution {
public:

    struct Trie{
        bool finish;
        Trie* next[10]; // 26가지 알파벳에 대한 트라이

        // 생성자
        Trie() : finish(false) {
            memset(next, 0, sizeof(next));
        }

        // 소멸자
        ~Trie() {
            for (int i = 0; i < 10; i++)
                if (next[i])
                    delete next[i];
        }

        void insert(const char* key) {
            if (*key == '\0')
                finish = true;
            else {
                int curr = *key - '0';
                if (next[curr] == NULL)
                    next[curr] = new Trie();
                next[curr]->insert(key + 1);
            }
        }

        int findDepth(const char* key){
            if(*key == '\0') return 0;

            int curr = *key - '0';
            if (next[curr] == NULL) return 0;
            return next[curr]->findDepth(key + 1) + 1;
        }

    };

    int longestCommonPrefix(vector<int>& arr1, vector<int>& arr2) {
        int result = 0;

        int len1 = arr1.size();
        int len2 = arr2.size();
        Trie *trie = new Trie();

        for(int i = 0; i < len1; i++){
            trie->insert(to_string(arr1[i]).c_str());
        }

        for (int i = 0; i < len2; ++i) {
            string str = to_string(arr2[i]);
            const char* c = str.c_str();

            result = max(result, trie->findDepth(c));
        }
        return result;
    }

};