koenjazh-CNfresde
짬뽕얼큰하게의 맨땅에 헤딩 :: '알고리즘' 카테고리의 글 목록 (6 Page)

Word Subsets

알고리즘 2025. 3. 4. 08:54

Leetcode Problem:

Summary

  • Given two string arrays, find all the universal strings in the first array that can form a subset of every string in the second array.

Approach

  • The approach used is to first count the frequency of each character in all strings of the second array
  • Then, for each string in the first array, check if it can form a subset of every string in the second array by comparing the frequency of each character in the string with the minimum count from the second array
  • If a string can form a subset of every string in the second array, it is added to the result.

Complexity

  • O(n * m * 26) where n is the number of strings in the first array, m is the number of strings in the second array, and 26 is the number of lowercase English letters.

Explanation

  • The solution uses a character count array `charCnt` to store the minimum frequency of each character in the second array
  • It then iterates over each string in the first array and checks if it can form a subset of every string in the second array by comparing the frequency of each character in the string with the minimum count from the second array
  • If a string can form a subset of every string in the second array, it is added to the result.

Solution Code:


class Solution {
public:
    int charCnt[128];
    vector wordSubsets(vector& words1, vector& words2) {
        for(string word : words2){
            int tmpCnt[128] = {0};
            for(char c : word){
                tmpCnt[c]++;
            }
            for(int i = 'a' ; i <= 'z'; i++){
                charCnt[i] = max(charCnt[i], tmpCnt[i]);
            }
        }
        vector ans;
        for(string word : words1){
            int tmpCnt[128] = {0};
            for(char c : word){
                tmpCnt[c]++;
            }
            bool isSubset = true;
            for(int i = 'a' ; i <= 'z'; i++){
                if(charCnt[i] == 0) continue;
                if(tmpCnt[i] < charCnt[i]){
                    isSubset = false;
                    break;
                }
            }
            if(isSubset){
                ans.push_back(word);
            }
        }
        return ans;
    }
};

'알고리즘' 카테고리의 다른 글

Find the Prefix Common Array of Two Arrays  (0) 2025.03.04
Construct K Palindrome Strings  (0) 2025.03.04
Counting Words With a Given Prefix  (0) 2025.03.04
Count Prefix and Suffix Pairs I  (0) 2025.03.04
String Matching in an Array  (0) 2025.03.04
블로그 이미지

짬뽕얼큰하게

,

Counting Words With a Given Prefix

알고리즘 2025. 3. 4. 08:50

Leetcode Problem:

Summary

  • Find the number of strings in the array that contain a given prefix.

Approach

  • The solution uses a simple loop to iterate over each word in the array
  • For each word, it checks if the prefix is present by comparing characters one by one
  • If the prefix is found, it increments the answer counter.

Complexity

  • O(n*m) where n is the number of words and m is the length of the prefix.

Explanation

  • The solution works by iterating over each word in the array and comparing it with the prefix
  • It uses two nested loops to compare characters one by one
  • The outer loop iterates over each word, and the inner loop compares characters up to the length of the prefix
  • If the prefix is found, it increments the answer counter.

Solution Code:


class Solution {
public:
    int prefixCount(vector& words, string pref) {
        int ans = 0;
        for(string word : words){
            int i = 0;
            for( ; i < pref.size(); i++){
                if(pref[i] != word[i]){
                    break;
                }
            }
            if(i == pref.size()){
                ans++;
            }
        }
        return ans;
    }
};

'알고리즘' 카테고리의 다른 글

Construct K Palindrome Strings  (0) 2025.03.04
Word Subsets  (0) 2025.03.04
Count Prefix and Suffix Pairs I  (0) 2025.03.04
String Matching in an Array  (0) 2025.03.04
Minimum Number of Operations to Move All Balls to Each Box  (0) 2025.03.04
블로그 이미지

짬뽕얼큰하게

,

Count Prefix and Suffix Pairs I

알고리즘 2025. 3. 4. 08:48

Leetcode Problem:

Summary

  • This solution is designed to count the number of index pairs (i, j) where i < j and isPrefixAndSuffix(words[i], words[j]) is true.

Approach

  • The solution uses a nested loop approach to iterate over each pair of words in the input array
  • It checks if each word is a prefix and suffix of every other word in the array
  • The isPrefixAndSuffix function is used to check this condition
  • The time complexity of this approach is O(n^2 * m) where n is the number of words and m is the maximum length of a word.

Complexity

  • O(n^2 * m)

Explanation

  • The solution starts by initializing a variable ans to 0, which will be used to store the count of index pairs
  • It then iterates over each word in the input array using a for loop
  • For each word, it iterates over the rest of the words in the array using another for loop
  • For each pair of words, it checks if the word is a prefix and suffix of the other word using the isPrefixAndSuffix function
  • If it is, it increments the ans variable
  • Finally, it returns the ans variable at the end of the function.

Solution Code:


class Solution {
public:
    bool isPrefixAndSuffix(string str1, string str2){
        if(str1.size() > str2.size()) return false;
        for(int i = 0 ; i < str1.size(); i++){
            if(str1[i] != str2[i])return false;
            if(str1[i] != str2[str2.size() - str1.size() + i]) return false;
        }
        return true;
    }
    int countPrefixSuffixPairs(vector& words) {
        int ans = 0;
        for(int i = 0 ; i < words.size(); i++){
            for(int j = i + 1 ; j < words.size(); j++){
                if(isPrefixAndSuffix(words[i], words[j])){
                    ans++;
                }
            }
        }
        return ans;
    }
};

'알고리즘' 카테고리의 다른 글

Word Subsets  (0) 2025.03.04
Counting Words With a Given Prefix  (0) 2025.03.04
String Matching in an Array  (0) 2025.03.04
Minimum Number of Operations to Move All Balls to Each Box  (0) 2025.03.04
Shifting Letters II  (0) 2025.03.04
블로그 이미지

짬뽕얼큰하게

,

String Matching in an Array

알고리즘 2025. 3. 4. 08:44

Leetcode Problem:

Summary

  • Given an array of strings, return all strings that are a substring of another word.

Approach

  • The solution iterates over each word in the input array and checks if it is a substring of any other word in the array
  • It uses nested loops to compare characters between words.

Complexity

  • O(n^3) where n is the number of words in the input array

Explanation

  • The solution iterates over each word in the input array and checks if it is a substring of any other word in the array
  • It uses nested loops to compare characters between words
  • The outer loop iterates over each word, the middle loop checks if the current word is a substring of any other word, and the inner loop compares characters between words
  • If a word is found to be a substring of another word, it is added to the result array and the middle loop is terminated to avoid unnecessary comparisons.

Solution Code:


class Solution {
public:
    vector stringMatching(vector& words) {
        vector ans;
        for(int i = 0 ; i < words.size(); i++){
            bool success = false;
            for(int j = 0; j < words.size(); j++){
                if(i == j) continue;
                for(int k = 0; k < words[j].size(); k++){
                    int l = 0;
                    for(; l < words[i].size(); l++){
                        if(words[j][k+l] != words[i][l]) break;
                    }
                    if(l == words[i].size()){
                        ans.push_back(words[i]);
                        success = true;
                        break;
                    }
                }
                if(success) break;
            }
        }
        return ans;
    }
};

'알고리즘' 카테고리의 다른 글

Counting Words With a Given Prefix  (0) 2025.03.04
Count Prefix and Suffix Pairs I  (0) 2025.03.04
Minimum Number of Operations to Move All Balls to Each Box  (0) 2025.03.04
Shifting Letters II  (0) 2025.03.04
Partition Array According to Given Pivot  (0) 2025.03.03
블로그 이미지

짬뽕얼큰하게

,

Minimum Number of Operations to Move All Balls to Each Box

알고리즘 2025. 3. 4. 08:41

Leetcode Problem:

Summary

  • Given a binary string representing boxes with balls, find the minimum number of operations needed to move all the balls to each box.

Approach

  • The approach is to first count the number of balls in each box and store it in the `ltor` and `rtol` arrays
  • Then, calculate the minimum number of operations needed to move all the balls to each box by adding the `ltor` and `rtol` values at each index.

Complexity

  • O(n), where n is the length of the binary string.

Explanation

  • The provided C++ solution uses two arrays, `ltor` and `rtol`, to store the cumulative count of balls from the left and right sides of each box
  • The minimum number of operations needed to move all the balls to each box is calculated by adding the `ltor` and `rtol` values at each index
  • This approach ensures that the minimum number of operations is calculated considering the initial state of the boxes.

Solution Code:


class Solution {
public:
    int ltor[2000];
    int rtol[2000];
    vector minOperations(string boxes) {
        vector ans;
        int oneCnt = 0;
        for(int i = 0 ; i < boxes.size() - 1; i++){
            if(boxes[i] == '1'){
                oneCnt++;
            }
            ltor[i+1] = ltor[i] + oneCnt;
        }
        oneCnt = 0;
        for(int i = boxes.size() - 1; i > 0 ; i--){
            if(boxes[i] == '1'){
                oneCnt++;
            }
            rtol[i-1] = rtol[i] + oneCnt;
        }
        for(int i = 0 ; i < boxes.size(); i++){
            ans.push_back(ltor[i] + rtol[i]);
        }
        return ans;
    }
};

'알고리즘' 카테고리의 다른 글

Count Prefix and Suffix Pairs I  (0) 2025.03.04
String Matching in an Array  (0) 2025.03.04
Shifting Letters II  (0) 2025.03.04
Partition Array According to Given Pivot  (0) 2025.03.03
Number of Ways to Split Array  (0) 2025.03.03
블로그 이미지

짬뽕얼큰하게

,

Shifting Letters II

알고리즘 2025. 3. 4. 08:38

Leetcode Problem:

Summary

  • Given a string s and a 2D integer array shifts, shift the characters in s from the start index to the end index forward if direction is 1, or backward if direction is 0.

Approach

  • This solution uses a prefix sum array to efficiently calculate the cumulative sum of shifts for each character
  • It then iterates over the string, adding the prefix sum to the current character's ASCII value and taking the modulus 26 to wrap around the alphabet.

Complexity

  • O(n + m) where n is the length of the string s and m is the number of shifts, as it needs to iterate over the string and the shifts array once.

Explanation

  • The prefix sum array pSum is used to store the cumulative sum of shifts for each character
  • For each shift, the sum of the character at the start index and the sum of the character at the end index plus the shift direction are added to pSum[start] and pSum[end+1] respectively
  • Then, the string is iterated over, and the prefix sum is added to the current character's ASCII value to get the shifted character
  • The modulus 26 is taken to wrap around the alphabet.

Solution Code:


class Solution {
public:
    int pSum[500001];
    int fb[2] = {25, 1};
    string shiftingLetters(string s, vector>& shifts) {
        for(int i = 0 ; i < shifts.size(); i++){
            int start = shifts[i][0];
            int end = shifts[i][1];
            int dir = shifts[i][2];
            pSum[start] += fb[dir];
            pSum[start] %= 26;
            pSum[end+1] += fb[dir ^ 1];
            pSum[end+1] %= 26;
            
        }

        string ans = "";
        for(int i = 0 ; i < s.size(); i++){
            pSum[i+1] += pSum[i];
            pSum[i] %= 26;
            unsigned char c = s[i] + pSum[i];
            if(c > 'z') c = 'a' + (c - 'z') - 1;
            if(c < 'a') c = 'z' - ('a' - c - 1);
            ans += c;
        }
        
        return ans;
    }
};

'알고리즘' 카테고리의 다른 글

String Matching in an Array  (0) 2025.03.04
Minimum Number of Operations to Move All Balls to Each Box  (0) 2025.03.04
Partition Array According to Given Pivot  (0) 2025.03.03
Number of Ways to Split Array  (0) 2025.03.03
Count Vowel Strings in Ranges  (0) 2025.03.03
블로그 이미지

짬뽕얼큰하게

,

Partition Array According to Given Pivot

알고리즘 2025. 3. 3. 12:50

Leetcode Problem:

Summary

  • Given an array of integers and a pivot value, rearrange the array such that all elements less than the pivot appear before all elements greater than the pivot, and elements equal to the pivot appear in between.

Approach

  • Separate the array into three lists: less than pivot, equal to pivot, and greater than pivot
  • Then, concatenate these lists to form the rearranged array.

Complexity

  • O(n), where n is the number of elements in the array
  • This is because each element in the array is visited once.

Explanation

  • This solution uses three lists to separate the array into three categories based on the pivot value
  • Then, it concatenates these lists to form the rearranged array
  • This approach ensures that all elements less than the pivot appear before all elements greater than the pivot, and elements equal to the pivot appear in between
  • The time complexity is O(n) because each element in the array is visited once.

Solution Code:


class Solution {
public:
    vector pivotArray(vector& nums, int pivot) {
        vector less;
        vector equal;
        vector greater;
        for(int i = 0 ; i < nums.size(); i++){
            if(nums[i] < pivot){
                less.push_back(nums[i]);
            } else if(nums[i] > pivot){
                greater.push_back(nums[i]);
            } else{
                equal.push_back(nums[i]);
            }
        }
        vector ans;
        ans.insert(ans.end(), less.begin(), less.end());
        ans.insert(ans.end(), equal.begin(), equal.end());
        ans.insert(ans.end(), greater.begin(), greater.end());
        return ans;
    }
};

'알고리즘' 카테고리의 다른 글

Minimum Number of Operations to Move All Balls to Each Box  (0) 2025.03.04
Shifting Letters II  (0) 2025.03.04
Number of Ways to Split Array  (0) 2025.03.03
Count Vowel Strings in Ranges  (0) 2025.03.03
Minimum Cost For Tickets  (0) 2025.03.03
블로그 이미지

짬뽕얼큰하게

,

Number of Ways to Split Array

알고리즘 2025. 3. 3. 09:07

Leetcode Problem:

Summary

  • The problem requires to find the number of valid splits in the given array
  • A valid split is when the sum of the first i+1 elements is greater than or equal to the sum of the last n-i-1 elements.

Approach

  • The approach used is to calculate the prefix sum of the array and then iterate over the array to check for valid splits
  • The prefix sum is calculated using a dynamic programming approach and stored in an array
  • Then, for each index i, the sum of the first i+1 elements is compared with the sum of the last n-i-1 elements
  • If the sum of the first i+1 elements is greater than or equal to the sum of the last n-i-1 elements, then the index i is considered as a valid split.

Complexity

  • O(n)

Explanation

  • The time complexity of the solution is O(n) because we are iterating over the array once to calculate the prefix sum and again to check for valid splits
  • The space complexity is also O(n) because we are storing the prefix sum in an array of size n.

Solution Code:


class Solution {
public:
    long long pSum[100000];
    int waysToSplitArray(vector& nums) {
        pSum[0] = nums[0];
        for(int i = 1 ; i < nums.size(); i++){
            pSum[i] = pSum[i-1] + nums[i];
        }
        int ans = 0;
        int last = nums.size() - 1;
        for(int i = 0; i < last; i++){
            if(pSum[i] >= pSum[last] - pSum[i]){
                ans++;
            }
        }
        return ans;
    }
};

'알고리즘' 카테고리의 다른 글

Shifting Letters II  (0) 2025.03.04
Partition Array According to Given Pivot  (0) 2025.03.03
Count Vowel Strings in Ranges  (0) 2025.03.03
Minimum Cost For Tickets  (0) 2025.03.03
Count Ways To Build Good Strings  (0) 2025.03.03
블로그 이미지

짬뽕얼큰하게

,

Count Vowel Strings in Ranges

알고리즘 2025. 3. 3. 09:04

Leetcode Problem:

Summary

  • Given a list of strings and queries, find the number of strings that start and end with a vowel.

Approach

  • Use a prefix sum array to store the count of strings that start and end with a vowel
  • Then, for each query, subtract the count of strings that start at the query's left index from the count of strings that end at the query's right index.

Complexity

  • O(n + m * q) where n is the number of strings, m is the maximum length of a string, and q is the number of queries.

Explanation

  • The prefix sum array is initialized with all zeros
  • Then, for each string, if the first and last characters are both vowels, increment the count at that index
  • Finally, for each query, subtract the count at the left index from the count at the right index to get the answer.

Solution Code:


class Solution {
public:
    int pSum[100002];

    bool isVowel(char c){
        if(c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u'){
            return true;
        }
        return false;
    }
    vector vowelStrings(vector& words, vector>& queries) {
        for(int i = 0 ; i < words.size(); i++){
            pSum[i+1] = pSum[i];
            string s = words[i];
            if(isVowel(s[0]) && isVowel(s[s.size() - 1])){
                pSum[i+1]++;
            }
        }
        vector ans;
        for(int i = 0 ; i < queries.size(); i++){
            ans.push_back(pSum[queries[i][1]+1] - pSum[queries[i][0]]);
        }
        return ans;
    }
};

'알고리즘' 카테고리의 다른 글

Partition Array According to Given Pivot  (0) 2025.03.03
Number of Ways to Split Array  (0) 2025.03.03
Minimum Cost For Tickets  (0) 2025.03.03
Count Ways To Build Good Strings  (0) 2025.03.03
Number of Ways to Form a Target String Given a Dictionary  (0) 2025.03.03
블로그 이미지

짬뽕얼큰하게

,

Minimum Cost For Tickets

알고리즘 2025. 3. 3. 09:00

Leetcode Problem:

Summary

  • The problem is to find the minimum cost of traveling a list of days given the costs of 1-day, 7-day, and 30-day passes.

Approach

  • Dynamic programming is used to solve this problem
  • The idea is to create a dp array where dp[i] represents the minimum cost to reach day i
  • The dp array is initialized with zeros and then filled up in a bottom-up manner
  • For each day, if the day is less than the current day in the days array, the cost is the same as the previous day
  • Otherwise, the cost is the minimum of the cost of buying a 1-day pass, a 7-day pass, and a 30-day pass for the current day.

Complexity

  • O(n) where n is the number of days.

Explanation

  • The dynamic programming approach is used to solve this problem efficiently
  • The dp array is filled up in a bottom-up manner, starting from day 1
  • For each day, if the day is less than the current day in the days array, the cost is the same as the previous day
  • Otherwise, the cost is the minimum of the cost of buying a 1-day pass, a 7-day pass, and a 30-day pass for the current day
  • This approach avoids the need to calculate the cost for each day multiple times, making it more efficient.

Solution Code:


class Solution {
public:
    int mincostTickets(vector& days, vector& costs) {
        int lastDay = days[days.size() - 1];
        vector dp(lastDay + 1, 0);
        
        int i = 0;
        for (int day = 1; day <= lastDay; day++) {
            if (day < days[i]) {
                dp[day] = dp[day - 1];
            } else {
                i++;
                dp[day] = min({dp[day - 1] + costs[0],
                               dp[max(0, day - 7)] + costs[1],
                               dp[max(0, day - 30)] + costs[2]});
            }
        }
     
        return dp[lastDay];
    }
};

'알고리즘' 카테고리의 다른 글

Number of Ways to Split Array  (0) 2025.03.03
Count Vowel Strings in Ranges  (0) 2025.03.03
Count Ways To Build Good Strings  (0) 2025.03.03
Number of Ways to Form a Target String Given a Dictionary  (0) 2025.03.03
Maximum Sum of 3 Non-Overlapping Subarrays  (0) 2025.03.03
블로그 이미지

짬뽕얼큰하게

,

공지사항

글 보관함

달력

«   2025/04   »
일 월 화 수 목 금 토
1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30

티스토리툴바