'Algorithm' 태그의 글 목록 (21 Page)

Extra Characters in a String

알고리즘 2025. 2. 12. 09:04

Leetcode Problem:
Extra Characters in a String

Summary

Given a string s and a dictionary of words, find the minimum number of extra characters left over if the string is broken into non-overlapping substrings present in the dictionary.

Approach

Dynamic programming approach, where a 1D array dp is used to store the minimum number of extra characters for each prefix of the string
The function go recursively tries to match the current prefix with each word in the dictionary, and updates the dp array accordingly.

Complexity

O(n*m*len(word)) where n is the length of the string, m is the number of words in the dictionary, and len(word) is the length of each word in the dictionary.

Explain

The function go takes a string s, a dictionary of words dict, and an integer i as input
It first checks if the current prefix of the string has been processed before (i.e., dp[i] is not -1)
If not, it sets dp[i] to 1 (for the extra character) and recursively calls itself for the next character
Then it tries to match the current prefix with each word in the dictionary, and updates dp[i] with the minimum of its current value and the result of the recursive call for the next character plus the length of the current word
The function minExtraChar initializes the dp array and calls the function go with the initial prefix as an empty string.

Solution Code:


class Solution {
public:
    int dp[51];
    int go(string & s, vector& dict, int i){
        if(i == s.size()) return 0;

        if (dp[i] == -1){
            dp[i] = 1 + go(s, dict, i+1);
            for(auto &w: dict){
                if(s.compare(i, w.size(), w) == 0){
                    dp[i] = min(dp[i], go(s, dict, i+w.size()));
                }
            }
        }
        return dp[i];

    }
    int minExtraChar(string s, vector& dictionary) {
        memset(dp, -1, sizeof(dp));
        return go(s, dictionary, 0);
    }
};

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

Max Sum of a Pair With Equal Sum of Digits (0)	2025.02.12
Find the Length of the Longest Common Prefix (0)	2025.02.12
K-th Smallest in Lexicographical Order (0)	2025.02.12
Largest Number (0)	2025.02.12
XOR Queries of a Subarray (0)	2025.02.12

짬뽕얼큰하게

,

K-th Smallest in Lexicographical Order

알고리즘 2025. 2. 12. 09:01

Leetcode Problem:
K-th Smallest in Lexicographical Order

Summary

Given two integers n and k, return the kth lexicographically smallest integer in the range [1, n].

Approach

The solution uses a binary search approach to find the kth lexicographically smallest number
It first calculates the number of numbers less than or equal to n that can be formed by appending a digit from 1 to 9 to the current number
Then it recursively finds the kth lexicographically smallest number by finding the kth number that can be formed by appending a digit from 1 to 9 to the current number.

Complexity

O(log(n))

Explain

The solution consists of two main functions: findKthNumber and findKthNumber
The findKthNumber function takes an integer n and an integer k as input and returns the kth lexicographically smallest number
The findKthNumber function uses a binary search approach to find the kth lexicographically smallest number
It first calculates the number of numbers less than or equal to n that can be formed by appending a digit from 1 to 9 to the current number
Then it recursively finds the kth lexicographically smallest number by finding the kth number that can be formed by appending a digit from 1 to 9 to the current number
The second findKthNumber function is used to calculate the number of numbers less than or equal to n that can be formed by appending a digit from 1 to 9 to the current number.

Solution Code:


class Solution {
public:
    int findKthNumber(int n, int k) {
        int result = 1;
        while (k > 1) {
            int count = findKthNumber(result, result + 1, n);
            if (count < k) {
                result++;
                k -= count;
            } else {
                result *= 10;
                k--;
            }
        }
        return result;
    }
    int findKthNumber(long p, long q, long n) {
        int result = 0;
        while (p <= n) {
            result += min(q, n + 1) - p;
            p *= 10;
            q *= 10;
        }
        return result;
    }
};

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

Find the Length of the Longest Common Prefix (0)	2025.02.12
Extra Characters in a String (0)	2025.02.12
Largest Number (0)	2025.02.12
XOR Queries of a Subarray (0)	2025.02.12
Count the Number of Consistent Strings (0)	2025.02.12

짬뽕얼큰하게

,

Largest Number

알고리즘 2025. 2. 12. 08:57

Leetcode Problem:
Largest Number

Summary

Given a list of non-negative integers, arrange them to form the largest number and return it as a string.

Approach

The approach used is to first convert all the numbers into strings, then sort them in descending order based on a custom comparison function
The comparison function concatenates each pair of strings in both orders (ab and ba) and returns the one that results in the larger number
After sorting, the strings are concatenated in reverse order to form the largest possible number.

Complexity

O(n log n) due to the sorting operation, where n is the number of elements in the input list.

Explain

The solution code first converts all the numbers in the input list into strings
It then defines a custom comparison function `cmp` that takes two strings `a` and `b` as input
This function concatenates each pair of strings in both orders (ab and ba) and returns the one that results in the larger number
The `largestNumber` function then sorts the list of strings using this comparison function and concatenates them in reverse order to form the largest possible number
Finally, it checks if the resulting number starts with '0' and returns '0' if it does, to handle the case where all the numbers are zeros.

Solution Code:


class Solution {
public:
    static bool cmp(string a, string b){
        string aa = a + b;
        string bb = b + a;
        return aa < bb;
    }
    string largestNumber(vector& nums) {
        vector str_nums;
        for(int i = 0 ; i < nums.size(); i++){
            str_nums.push_back(to_string(nums[i]));
        }
        sort(str_nums.begin(), str_nums.end(), cmp);
        string ans = "";
        for(int i = str_nums.size() - 1; i >= 0 ; i--){
            ans += str_nums[i];
        }
        if (ans.find("0") == 0) return "0";
        return ans;
    }
};

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

Extra Characters in a String (0)	2025.02.12
K-th Smallest in Lexicographical Order (0)	2025.02.12
XOR Queries of a Subarray (0)	2025.02.12
Count the Number of Consistent Strings (0)	2025.02.12
Minimum Bit Flips to Convert Number (0)	2025.02.12

짬뽕얼큰하게

,

XOR Queries of a Subarray

알고리즘 2025. 2. 12. 08:54

Leetcode Problem:
XOR Queries of a Subarray

Summary

Given an array of positive integers and queries where each query is a range, compute the XOR of elements in the range for each query.

Approach

The approach is to first compute the XOR of all elements in the array and then for each query, compute the XOR of the elements in the range by XORing the element at the end of the range with the XOR of the elements up to the second last element in the range.

Complexity

O(n + q) where n is the size of the array and q is the number of queries

Explain

The solution first computes the XOR of all elements in the array by iterating over the array and XORing each element with the previous one
Then for each query, it computes the XOR of the elements in the range by XORing the element at the end of the range with the XOR of the elements up to the second last element in the range
This is done by accessing the element at the end of the range and the element at the position before the end of the range, and XORing them
The result is then added to the answer vector.

Solution Code:


class Solution {
public:
    vector xorQueries(vector& arr, vector>& queries) {
        vector ans;
        for(int i = 1 ; i < arr.size(); i++){
            arr[i] = arr[i] ^ arr[i-1];
        }
        for(int i = 0 ; i < queries.size(); i++) {
            int a = queries[i][0];
            int b = queries[i][1];
            ans.push_back(arr[b] ^ (a-1 < 0 ? 0 : arr[a-1]));
        }
        return ans;
    }
};

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

K-th Smallest in Lexicographical Order (0)	2025.02.12
Largest Number (0)	2025.02.12
Count the Number of Consistent Strings (0)	2025.02.12
Minimum Bit Flips to Convert Number (0)	2025.02.12
Insert Greatest Common Divisors in Linked List (0)	2025.02.12

짬뽕얼큰하게

,

Count the Number of Consistent Strings

알고리즘 2025. 2. 12. 08:51

Leetcode Problem:
Count the Number of Consistent Strings

Summary

Count the number of consistent strings in a given array of words, where a string is consistent if all characters appear in the allowed string.

Approach

The solution uses a boolean array to track the presence of each character in the allowed string
It then iterates over each word in the array, checking if each character in the word is present in the allowed string
If a character is not present, the word is not consistent and is not counted.

Complexity

O(n*m), where n is the length of the allowed string and m is the maximum length of a word in the array.

Explain

The solution works by first initializing a boolean array `allow` of size 256, where each index corresponds to a lowercase English letter
It then iterates over each character in the allowed string, setting the corresponding index in the `allow` array to `true`
The solution then iterates over each word in the array, checking if each character in the word is present in the `allow` array
If a character is not present, the word is not consistent and is not counted
The number of consistent words is then returned.

Solution Code:


class Solution {
public:
    bool allow[256];
    int countConsistentStrings(string allowed, vector& words) {
        for(int i = 0 ; i < allowed.size(); i++){
            allow[allowed[i]] = true;
        }
        int ans = 0;
        for(int i = 0 ; i < words.size(); i++){
            bool success = true;
            for(int j = 0; j < words[i].size(); j++){
                if (!allow[words[i][j]]){
                    success = false;
                    break;
                }
            }
            if (success){
                ans++;
            }
        }
        return ans;
    }
};

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

Largest Number (0)	2025.02.12
XOR Queries of a Subarray (0)	2025.02.12
Minimum Bit Flips to Convert Number (0)	2025.02.12
Insert Greatest Common Divisors in Linked List (0)	2025.02.12
Spiral Matrix IV (0)	2025.02.12

짬뽕얼큰하게

,

Minimum Bit Flips to Convert Number

알고리즘 2025. 2. 12. 08:48

Leetcode Problem:
Minimum Bit Flips to Convert Number

Summary

Find the minimum number of bit flips to convert start to goal.

Approach

This solution works by continuously dividing both start and goal by 2 (using bitwise right shift) until they are both 0
In each iteration, it checks if the least significant bit of start and goal are different
If they are, it increments the answer by 1
This is because flipping the least significant bit of either start or goal (or both) requires one bit flip.

Complexity

O(log min(start, goal))

Explain

The time complexity of this solution is O(log min(start, goal)) because in each iteration, the size of start and goal is halved
The space complexity is O(1) because only a constant amount of space is used.

Solution Code:


class Solution {
public:
    int minBitFlips(int start, int goal) {
        int ans = 0;
        while(!(start == 0 && goal == 0)){
            if((start & 1) != (goal & 1)) ans++;
            start >>= 1;
            goal >>= 1;
        }
        return ans;
    }
};

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

XOR Queries of a Subarray (0)	2025.02.12
Count the Number of Consistent Strings (0)	2025.02.12
Insert Greatest Common Divisors in Linked List (0)	2025.02.12
Spiral Matrix IV (0)	2025.02.12
Linked List in Binary Tree (0)	2025.02.12

짬뽕얼큰하게

,

Insert Greatest Common Divisors in Linked List

알고리즘 2025. 2. 12. 08:45

Leetcode Problem:
Insert Greatest Common Divisors in Linked List

Summary

Inserting greatest common divisors between adjacent nodes in a linked list

Approach

The approach used is to traverse the linked list and for each pair of adjacent nodes, calculate the greatest common divisor (GCD) using the Euclidean algorithm
A new node is then inserted between the two nodes with the calculated GCD
The process is repeated until all nodes have been processed.

Complexity

O(n), where n is the number of nodes in the linked list

Explain

The provided C++ code defines a solution to the problem
The `_gcd` function calculates the GCD of two numbers using the Euclidean algorithm
The `insertGreatestCommonDivisors` function traverses the linked list, calculates the GCD of each pair of adjacent nodes, and inserts a new node with the calculated GCD between the two nodes
The process is repeated until all nodes have been processed, resulting in a linked list with the GCDs inserted between adjacent nodes.

Solution Code:


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    int _gcd(int a, int b){
        if(a % b == 0) return b;
        return _gcd(b, a%b);
    }
    ListNode* insertGreatestCommonDivisors(ListNode* head) {
        ListNode* ptr = head;
        while(ptr->next != nullptr){
            int a = ptr->val;
            int b = ptr->next->val;
            ListNode* newNode = new ListNode(_gcd(a, b), ptr->next);
            ptr->next = newNode;
            ptr = newNode->next;
        }
        return head;
    }
};

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

Count the Number of Consistent Strings (0)	2025.02.12
Minimum Bit Flips to Convert Number (0)	2025.02.12
Spiral Matrix IV (0)	2025.02.12
Linked List in Binary Tree (0)	2025.02.12
Remove All Occurrences of a Substring (0)	2025.02.11

짬뽕얼큰하게

,

Spiral Matrix IV

알고리즘 2025. 2. 12. 08:41

Leetcode Problem:
Spiral Matrix IV

Summary

Generate a spiral matrix from a linked list of integers

Approach

Use a spiral traversal algorithm to fill the matrix in a clockwise direction

Complexity

O(R*C + N)

Explain

The solution uses a spiral traversal algorithm to fill the matrix in a clockwise direction
The algorithm starts from the top-left corner of the matrix and moves in a spiral pattern until all elements have been visited
The matrix is represented as a 2D vector, and the algorithm uses two arrays `dy` and `dx` to keep track of the direction of movement
The `R` and `C` variables represent the number of rows and columns in the matrix, respectively
The algorithm also uses a `while` loop to iterate through the linked list and fill the matrix with the corresponding values
The remaining empty spaces in the matrix are filled with -1.

Solution Code:


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    vector> ans;
    
    int R, C;
    vector> spiralMatrix(int m, int n, ListNode* head) {
        int dy[] = {0, 1, 0, -1};
        int dx[] = {1, 0, -1, 0};
        R = m;
        C = n;

        vector> ans(m, vector(n, -1));
        int r = 0;
        int c = 0;
        int dir = 0;
        while(head){
            ans[r][c] = head->val;
            int nr = r + dy[dir];
            int nc = c + dx[dir];
            if (nr < 0 || nr >= R || nc < 0 || nc >= C || ans[nr][nc] != -1){
                dir = (dir + 1) %4;
                nr = r + dy[dir];
                nc = c + dx[dir];
            }
            r = nr;
            c = nc;
            head = head->next;
        }
        return ans;
    }
};

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

Minimum Bit Flips to Convert Number (0)	2025.02.12
Insert Greatest Common Divisors in Linked List (0)	2025.02.12
Linked List in Binary Tree (0)	2025.02.12
Remove All Occurrences of a Substring (0)	2025.02.11
Delete Nodes From Linked List Present in Array (0)	2025.02.11

짬뽕얼큰하게

,

Linked List in Binary Tree

알고리즘 2025. 2. 12. 08:38

Leetcode Problem:
Linked List in Binary Tree

Summary

Check if all elements in a linked list are present in a binary tree

Approach

This solution first traverses the linked list and stores its elements in a vector
Then it creates a hash table to store the indices of the elements in the vector
It then checks if the binary tree contains all the elements of the linked list by traversing the tree and using the hash table to keep track of the current position in the linked list.

Complexity

O(n*m) where n is the number of nodes in the binary tree and m is the number of nodes in the linked list

Explain

The solution works by first storing the elements of the linked list in a vector
It then creates a hash table to store the indices of the elements in the vector
This is done by iterating over the vector and storing the index of each element in the hash table
The hash table is used to keep track of the current position in the linked list when traversing the binary tree
If the binary tree contains all the elements of the linked list, the solution returns true
Otherwise, it returns false.

Solution Code:


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector listNode;
    int pi[100];
    int match;
    bool traversal(TreeNode* root, int match){
        if (match == listNode.size()) return true;
        if(root == nullptr) return false;
        while(match != 0 && root->val != listNode[match]){
            match = pi[match -1];
        }
        if(root->val == listNode[match]){
            match++;
        }
        if (traversal(root->left, match)){
            return true;
        }
        if (traversal(root->right, match)){
            return true;
        }
        return false;
    }
    bool isSubPath(ListNode* head, TreeNode* root) {
        while(head){
            listNode.push_back(head->val);
            head = head->next;
        }
        match = 0;
        for(int i = 1; i < listNode.size(); i++){
            while(match != 0 && listNode[i] != listNode[match]){
                match = pi[match-1];
            }
            if(listNode[i] == listNode[match]){
                match++;
            }
            pi[i] = match;
        }
        if (traversal(root, 0)){
            return true;
        }
        return false;
    }
};

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

Insert Greatest Common Divisors in Linked List (0)	2025.02.12
Spiral Matrix IV (0)	2025.02.12
Remove All Occurrences of a Substring (0)	2025.02.11
Delete Nodes From Linked List Present in Array (0)	2025.02.11
Find Missing Observations (0)	2025.02.11

짬뽕얼큰하게

,

Remove All Occurrences of a Substring

알고리즘 2025. 2. 11. 23:11

Leetcode Problem:
Remove All Occurrences of a Substring

Summary

Given a string s and a substring part, remove all occurrences of part from s

Approach

Use a stack data structure to keep track of the characters in s and check for occurrences of part
If part is found, remove it from the stack by popping the characters one by one.

Complexity

O(n*m) where n is the length of s and m is the length of part

Explain

The solution iterates over the string s and checks for occurrences of part by comparing the characters at the end of part with the characters in the stack
If part is found, it removes it from the stack by popping the characters one by one
The time complexity is O(n*m) because in the worst case, the stack size can be n and the number of occurrences of part can be m.

Solution Code:


class Solution {
public:
    vector st;
    string removeOccurrences(string s, string part) {
        for(int i = 0 ; i < s.size(); i++){
            st.push_back(s[i]);
            if(st.size() >= part.size()){
                bool success = true;
                for(int j = 0; j < part.size(); j++){
                    if(st[st.size()-j -1] != part[part.size() - j - 1]){
                        success = false;
                        break;
                    }
                }
                if(success){
                    for(int j = 0 ; j < part.size(); j++){
                        st.pop_back();
                    }
                }
            }
        }
        string ans = "";
        for(int i = 0 ; i < st.size(); i++){
            ans += st[i];
        }
        return ans;
    }
};

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

Spiral Matrix IV (0)	2025.02.12
Linked List in Binary Tree (0)	2025.02.12
Delete Nodes From Linked List Present in Array (0)	2025.02.11
Find Missing Observations (0)	2025.02.11
Walking Robot Simulation (0)	2025.02.11

짬뽕얼큰하게

,

일	월	화	수	목	금	토
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

'Algorithm'에 해당되는 글 281건

Leetcode Problem: Extra Characters in a String

Summary

Approach

Complexity

Explain

Solution Code:

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

Leetcode Problem: K-th Smallest in Lexicographical Order

Summary

Approach

Complexity

Explain

Solution Code:

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

Leetcode Problem: Largest Number

Summary

Approach

Complexity

Explain

Solution Code:

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

Leetcode Problem: XOR Queries of a Subarray

Summary

Approach

Complexity

Explain

Solution Code:

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

Leetcode Problem: Count the Number of Consistent Strings

Summary

Approach

Complexity

Explain

Solution Code:

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

Leetcode Problem: Minimum Bit Flips to Convert Number

Summary

Approach

Complexity

Explain

Solution Code:

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

Leetcode Problem: Insert Greatest Common Divisors in Linked List

Summary

Approach

Complexity

Explain

Solution Code:

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

Leetcode Problem: Spiral Matrix IV

Summary

Approach

Complexity

Explain

Solution Code:

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

Leetcode Problem: Linked List in Binary Tree

Summary

Approach

Complexity

Explain

Solution Code:

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

Leetcode Problem: Remove All Occurrences of a Substring

Summary

Approach

Complexity

Explain

Solution Code:

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

공지사항

카테고리

태그목록

글 보관함

달력

링크

짬뽕얼큰하게

LATEST FROM OUR BLOG

LATEST COMMENTS

Leetcode Problem:
Extra Characters in a String

Leetcode Problem:
K-th Smallest in Lexicographical Order

Leetcode Problem:
Largest Number

Leetcode Problem:
XOR Queries of a Subarray

Leetcode Problem:
Count the Number of Consistent Strings

Leetcode Problem:
Minimum Bit Flips to Convert Number

Leetcode Problem:
Insert Greatest Common Divisors in Linked List

Leetcode Problem:
Spiral Matrix IV

Leetcode Problem:
Linked List in Binary Tree

Leetcode Problem:
Remove All Occurrences of a Substring