Leetcode 1023: Camelcase Matching
You are given a list of query strings and a pattern. A query string matches the pattern if you can insert lowercase English letters into the pattern such that it becomes the query string. Each character from the pattern must be placed in order without changing its relative positions, and you may not add any characters that are not in the pattern.
Problem
Approach
Steps
Complexity
Input: The input consists of a list of query strings and a string pattern.
Example: queries = ["ABCdEF", "AbCdEFG", "ACE", "AcEfG", "AcdFEG"], pattern = "ACE"
Constraints:
• 1 <= pattern.length, queries.length <= 100
• 1 <= queries[i].length <= 100
• queries[i] and pattern consist of English letters.
Output: The output is a boolean array where each element indicates whether the corresponding query string matches the pattern or not.
Example: Output: [true, true, true, false, false]
Constraints:
• The output array must contain a boolean value for each query string.
Goal: We need to check if we can insert lowercase letters into the pattern in a way that the pattern becomes the query string. This can be done by scanning both the pattern and query string simultaneously and ensuring the pattern's characters appear in the same order in the query.
Steps:
• 1. For each query, iterate through the characters of the query and the pattern simultaneously.
• 2. Check if each character in the query matches the corresponding character in the pattern, skipping over any lowercase characters in the query.
• 3. If all characters in the pattern are matched in order, return true for that query; otherwise, return false.
Goal: Ensure that the solution works efficiently for the given input size.
Steps:
• The solution should be able to handle up to 100 queries, each up to 100 characters long.
Assumptions:
• The pattern and query strings consist only of uppercase and lowercase English letters.
• Input: Input: queries = ["ABCdEF", "AbCdEFG", "ACE", "AcEfG", "AcdFEG"], pattern = "ACE"
• Explanation: In this case, 'ABCdEF' can be formed by inserting 'B' and 'D' into the pattern 'ACE', so the output is true. 'AbCdEF' can be formed by inserting 'b', 'C' and 'G', so the output is true. 'ACE' is already equal to the pattern, so the output is true. 'AcEfG' doesn't match the pattern because of extra characters in the middle, so the output is false. 'AcdFEG' doesn't match because of extra characters and incorrect ordering, so the output is false.
Approach: The approach is to use a two-pointer technique to check if the characters of the pattern appear in the correct order in each query string, allowing for lowercase characters to be inserted.
Observations:
• We can utilize two pointers, one for the pattern and one for the query string, to verify if the pattern characters appear in the correct order in the query.
• By iterating through the query string and matching characters from the pattern, we can determine if the pattern is a subsequence of the query.
Steps:
• 1. Initialize a pointer for the pattern and for each query.
• 2. Iterate through the characters of the query and the pattern.
• 3. For each character in the query, if it matches the current character in the pattern, move the pattern pointer to the next character.
• 4. If all characters in the pattern are matched in the query in order, return true for that query, otherwise return false.
Empty Inputs:
• If the query or pattern is empty, return false.
Large Inputs:
• If there are large numbers of queries or very long query strings, the algorithm should still perform efficiently.
Special Values:
• Handle cases where the query contains only lowercase letters or the pattern contains only uppercase letters.
Constraints:
• Ensure the solution handles edge cases, such as patterns and queries with special characters.
vector<bool> camelMatch(vector<string>& queries, string pattern) {
vector<bool> res;
for(string q: queries) {
bool ret = match(q, pattern);
res.push_back(ret);
}
return res;
}
bool match(string q, string p) {
int j = 0;
for(int i = 0; i < q.size(); i++) {
if(j < p.size()&&q[i] == p[j]) {
j++;
continue;
}else if(q[i] >= 'A' &&
q[i] <= 'Z')
return false;
}
return j == p.size();
}
1 : Function Definition
vector<bool> camelMatch(vector<string>& queries, string pattern) {
Define the function `camelMatch` which takes a list of queries and a string pattern to check if the queries match the camelCase pattern.
2 : Variable Initialization
vector<bool> res;
Initialize a result vector `res` to store boolean values indicating whether each query matches the pattern.
3 : Looping
for(string q: queries) {
Iterate over each string in the `queries` list.
4 : Function Call
bool ret = match(q, pattern);
Call the helper function `match` to check if the query string `q` matches the pattern.
5 : Result Collection
res.push_back(ret);
Store the result of the `match` function (true or false) into the `res` vector.
6 : Return Statement
return res;
Return the result vector containing the match status for each query.
7 : Helper Function Definition
bool match(string q, string p) {
Define the helper function `match` to check if a single query string matches the camelCase pattern.
8 : Variable Initialization
int j = 0;
Initialize an index `j` to track the position in the pattern string `p`.
9 : Looping
for(int i = 0; i < q.size(); i++) {
Iterate over each character in the query string `q`.
10 : Character Comparison
if(j < p.size()&&q[i] == p[j]) {
Check if the current character in `q` matches the current character in `p`.
11 : Index Update
j++;
Increment the index `j` to move to the next character in the pattern.
12 : Continue
continue;
Continue to the next iteration of the loop if the characters match.
13 : Condition Check
}else if(q[i] >= 'A' &&
Check if the character in `q` is an uppercase letter.
14 : Condition Check
q[i] <= 'Z')
Ensure the character is within the range of uppercase letters.
15 : Early Return
return false;
Return `false` if an uppercase letter in `q` is encountered that doesn't match the pattern.
16 : Return Statement
return j == p.size();
Return `true` if all characters in the pattern have been matched; otherwise, return `false`.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(m * n)
Description: The time complexity is O(m * n) where m is the number of queries and n is the length of each query. In the worst case, we need to compare each query string with the pattern.
Best Case: O(1)
Worst Case: O(1)
Description: The space complexity is O(1) because we are using only a few additional variables for the two pointers and the result.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus