1023. Camelcase Matching
Problem Description
The problem gives us an array of strings called queries
and a single string called pattern
. Our goal is to determine which strings in the queries
array match the pattern
. We say that a query string matches the pattern if it's possible to insert lowercase English letters into the pattern such that after insertion, the pattern is equal to the query. Importantly, these insertions can happen at any index within the pattern, but we cannot add any new characters into the query string. The output of the problem is a boolean array answer
where each element answer[i]
is true
if queries[i]
matches the pattern, otherwise false
.
For example, if the query is "FoBar"
and the pattern is "FB"
, we can see that by adding "o"
between "F"
and "B"
and appending "ar"
after "B"
, the pattern matches the query (after the insertions, the pattern would be "FoBar"
). Therefore, the answer for this query would be true
.
Intuition
The solution involves defining a match-checking function that uses two pointers to traverse and compare characters of the queries[i]
and pattern
one by one. By using an iterative process, we can validate if we can morph the pattern into each query.
The intuition for the solution is based on a couple of observations:
- The characters in both
queries[i]
andpattern
must match in order, and the matching characters inqueries[i]
must be in the same positions as inpattern
. Uppercase letters in the query are "anchors" that must be present and in the correct order in the pattern for a match to be possible. - Lowercase letters in
queries[i]
can be skipped because we're allowed to insert lowercase letters into the pattern. However, uppercase letters can't be skipped or inserted because they define the structure of the pattern that must be followed.
This allows us to implement a pointer-based approach:
- Initialize two pointers,
i
andj
, to traversequeries[i]
andpattern
, respectively. - Iterate over
queries[i]
with pointeri
, and for each character, check if it matches thej
th character ofpattern
. - If the characters match, move both pointers forward.
- If the characters do not match, and the
i
th character ofqueries[i]
is lowercase, we can attempt to skip it by moving pointeri
forward. - If we encounter an uppercase letter that doesn't match or we reach the end of
queries[i]
without fully traversing the pattern, that query does not match the pattern. - After pointer
j
has traversed the pattern, we need to ensure that all remaining characters inqueries[i]
are lowercase; otherwise, it means there are extra uppercase letters that make the query not match the pattern.
The match-checking function embodied the above logic, consistently applying it to every query in the array, thus creating the desired boolean output array.
The time complexity is linear with respect to the total number of characters in all queries and the length of the pattern, i.e., effectively O(n*m), where n is the number of queries and m is the length of the longest query string.
Learn more about Trie and Two Pointers patterns.
Solution Approach
The solution to the given problem involves creating a helper function, check(s, t)
, which is designed to determine if the string s
(a query) matches the string t
(the pattern). This function is crucial as it encapsulates the logic for matching based on the rules outlined in the problem description.
Helper Function: check(s, t)
This function uses the two-pointer technique, which is a common pattern used in string manipulation algorithms. Here's a breakdown of the check
function implementation using the s
and t
variables:
- Initialize two pointers:
i
starts at the beginning ofs
whilej
starts at the beginning oft
. - Iterate through
s
using the pointeri
:- If
s[i]
is a lowercase letter that does not matcht[j]
, incrementi
to skip it. This step embodies the rule that allows the insertion of lowercase letters. - If
s[i]
matchest[j]
, increment both pointersi
andj
to check the next characters since a match dictates we move in bothqueries
andpattern
. - If the characters do not match and
s[i]
is not a lowercase letter, returnfalse
as we can't insert uppercase letters or skip non-matching uppercase letters.
- If
- Once
j
has reached the end oft
, we check the remainder ofs
to ensure all leftover characters are lowercase. If we encounter an uppercase letter ori
hasn't yet reached the end ofs
, we returnfalse
as the additional characters can't be part of the pattern. - If
i
has reached the end ofs
, we returntrue
, indicating a successful match.
Main Logic
The main part of the solution consists of iterating over each string in the queries
array and applying the check
function:
- Use a list comprehension to iterate over all query strings in
queries
. - For each query, call the
check
function with the query and the pattern. - Convert the result of the
check
function into boolean values and store them in the final output list.
Time Complexity Analysis
The overall time complexity of the solution is O(n * m)
, where n
is the number of query strings in the queries
array, and m
is the length of the longest query string. This is because we must potentially traverse each character in each query string in the worst-case scenario, consuming linear time relative to the length of each individual query.
In summary, this approach is simple yet effective. It leverages the two-pointer pattern to navigate two strings simultaneously and verifies compliance with the pattern-matching rules. The algorithm is sharp in that it halts and decides as soon as a non-compliance is detected, ensuring optimal performance.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through an example to illustrate the solution approach described above.
Suppose we have the following queries
array and pattern
:
1queries = ["After", "AFter", "AFilter", "BFilter"] 2pattern = "AF"
To determine which query strings match the pattern, we apply the check
function to each one:
-
"After":
- Initialize pointers
i=0
andj=0
. Sincequeries[i] = 'A'
andpattern[j] = 'A'
, they match, and we increment both pointers. - Now
i=1
andj=1
, and we havequeries[i] = 'f'
andpattern[j] = 'F'
. They do not match because one is lowercase and the other is uppercase, but sincequeries[i]
is lowercase, we can skip it by incrementingi
. - With
i=2
andj=1
, we now havequeries[i] = 't'
andpattern[j] = 'F'
. The letters do not match, so we incrementi
as 't' is lowercase. - At
i=3
,j=1
, we havequeries[i] = 'e'
, still lowercase. We skip it. - Now
i=4
,j=1
, andqueries[i] = 'r'
. Another lowercase to skip. - Since
j
has not moved andi
reached the end ofqueries[i]
without matching 'F' frompattern
, we returnfalse
.
- Initialize pointers
-
"AFter":
- We set
i=0
andj=0
. They match ('A' with 'A'), so both pointers increment. - At
i=1
,j=1
,queries[i] = 'F'
andpattern[j] = 'F'
, they match, so increment both pointers again. - Now
i=2
, and sincej
has reached the end ofpattern
, we only need to check that the remaining characters inqueries[i]
are lowercase. - As 't', 'e', and 'r' are all lowercase, we move
i
to the end of the string. - Given that all conditions are satisfied,
i
has reached the end ofs
, andj
has reached the end oft
, we returntrue
.
- We set
-
"AFilter":
- Both pointers start at the beginning.
i=0
,j=0
, and 'A' matches 'A'. Both increment. - At
i=1
,j=1
, 'F' matches 'F'. Increment both again. i=2
now points to 'i' which is lowercase, so we can skip it.- Skipping all lowercase 'l', 't', 'e', 'r' by incrementing
i
each time. - Having processed all characters of
pattern
and ensured no uppercase letters in the remainingqueries[i]
, we returntrue
.
- Both pointers start at the beginning.
-
"BFilter":
- Start with
i=0
andj=0
. We find that 'B' doesn't match 'A' inpattern
and it's uppercase, which means we cannot skip it or change the pattern to match it. - Immediately we return
false
, as it's not possible for this query to match the pattern.
- Start with
The resulting list based on the check
function would be [false, true, true, false]
. This methodically applies the rules from the problem description to each query against the pattern. By utilizing this process, the check
function can efficiently validate pattern matching for each string in the queries
array.
Solution Implementation
1class Solution:
2 def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:
3 # Helper function to check if the query matches the pattern.
4 def matches_pattern(query: str, pattern: str) -> bool:
5 query_length = len(query)
6 pattern_length = len(pattern)
7 pattern_index = query_index = 0
8
9 # Traverse the pattern characters.
10 while pattern_index < pattern_length:
11 # Skip lower case characters from query that are not a part of the pattern.
12 while query_index < query_length and query[query_index] != pattern[pattern_index] and query[query_index].islower():
13 query_index += 1
14
15 # If query runs out of characters or does not match pattern character, return False.
16 if query_index == query_length or query[query_index] != pattern[pattern_index]:
17 return False
18
19 # Move to the next character in both query and pattern.
20 query_index += 1
21 pattern_index += 1
22
23 # All remaining characters in the query should be lowercase.
24 while query_index < query_length and query[query_index].islower():
25 query_index += 1
26
27 # True if the end of the query has been reached, False otherwise.
28 return query_index == query_length
29
30 # Use list comprehension to apply the helper function to all queries in the input list.
31 return [matches_pattern(query, pattern) for query in queries]
32
1class Solution {
2 // Function to check the list of strings 'queries' match the camel case pattern 'pattern'
3 public List<Boolean> camelMatch(String[] queries, String pattern) {
4 List<Boolean> matches = new ArrayList<>(); // List to hold the results
5 // Iterate over each query
6 for (String query : queries) {
7 // Add the result of matching each query with the pattern to the matches list
8 matches.add(isMatch(query, pattern));
9 }
10 return matches;
11 }
12
13 // Helper method to check if a single string 'query' matches the camel case 'pattern'
14 private boolean isMatch(String query, String pattern) {
15 int queryLength = query.length(); // Length of query string
16 int patternLength = pattern.length(); // Length of the pattern
17 int queryIndex = 0, patternIndex = 0; // Indices to track position within query and pattern
18
19 // Iterate through the characters in 'pattern'
20 while (patternIndex < patternLength) {
21 // Advance in 'query' while current character does not match the pattern character
22 // and it's a lowercase letter
23 while (queryIndex < queryLength && query.charAt(queryIndex) != pattern.charAt(patternIndex)
24 && Character.isLowerCase(query.charAt(queryIndex))) {
25 queryIndex++;
26 }
27 // If the end of 'query' is reached or characters do not match, the query doesn't follow the pattern
28 if (queryIndex == queryLength || query.charAt(queryIndex) != pattern.charAt(patternIndex)) {
29 return false;
30 }
31 // Move to the next character in both 'query' and 'pattern'
32 queryIndex++;
33 patternIndex++;
34 }
35
36 // After the end of 'pattern', all remaining characters in 'query' must be lowercase for it to be a match
37 while (queryIndex < queryLength && Character.isLowerCase(query.charAt(queryIndex))) {
38 queryIndex++;
39 }
40
41 // Return true if the end of 'query' is reached, otherwise false
42 return queryIndex == queryLength;
43 }
44}
45
1#include <vector>
2#include <string>
3using namespace std;
4
5class Solution {
6public:
7 // Function to determine if each query matches the given pattern
8 vector<bool> camelMatch(vector<string>& queries, string pattern) {
9 vector<bool> answers;
10 // Lambda function to check if a single query matches the pattern
11 auto matchesPattern = [](const string& query, const string& pattern) {
12 int queryLength = query.size();
13 int patternLength = pattern.size();
14 int queryIndex = 0, patternIndex = 0;
15
16 // Loop through each character in the pattern
17 while (patternIndex < patternLength) {
18 // Advance through the query string to find the match for the current pattern character
19 while (queryIndex < queryLength && query[queryIndex] != pattern[patternIndex] && islower(query[queryIndex])) {
20 ++queryIndex;
21 }
22
23 // Check if query ended or characters don't match
24 if (queryIndex == queryLength || query[queryIndex] != pattern[patternIndex]) {
25 return false;
26 }
27
28 // Move to the next character in both the query and the pattern
29 ++queryIndex;
30 ++patternIndex;
31 }
32
33 // All characters in the pattern are matched, check if the remaining characters in the query are all lowercase
34 while (queryIndex < queryLength && islower(query[queryIndex])) {
35 ++queryIndex;
36 }
37
38 // If we reached the end of the query, all checks are passed
39 return queryIndex == queryLength;
40 };
41
42 // Iterate through all the queries to check against the pattern
43 for (auto& query : queries) {
44 answers.push_back(matchesPattern(query, pattern));
45 }
46
47 return answers; // Return a vector with the results for each query
48 }
49};
50
1// Function to match camel case patterns within a set of query strings
2function camelMatch(queries: string[], pattern: string): boolean[] {
3 // Helper function to check if a single query matches the camel case pattern
4 const checkPattern = (query: string, pattern: string): boolean => {
5 const queryLength = query.length;
6 const patternLength = pattern.length;
7 let queryIndex = 0;
8 let patternIndex = 0;
9 // Iterate through both query and pattern
10 for (; patternIndex < patternLength; ++queryIndex, ++patternIndex) {
11 // Skip lowercase characters in query that do not match the current pattern character
12 while (queryIndex < queryLength &&
13 query[queryIndex] !== pattern[patternIndex] &&
14 query.charCodeAt(queryIndex) >= 97) { // ASCII 97 = 'a'
15 ++queryIndex;
16 }
17 // Pattern character does not match, or query ended before pattern
18 if (queryIndex === queryLength || query[queryIndex] !== pattern[patternIndex]) {
19 return false;
20 }
21 }
22 // Skip all trailing lowercase characters in the query
23 while (queryIndex < queryLength && query.charCodeAt(queryIndex) >= 97) {
24 ++queryIndex;
25 }
26 // If all characters of query are checked, it's a match
27 return queryIndex == queryLength;
28 };
29
30 // Array to store results for each query
31 const results: boolean[] = [];
32 // Check each query and add the result to the results array
33 for (const query of queries) {
34 results.push(checkPattern(query, pattern));
35 }
36 return results;
37}
38
Time and Space Complexity
The given code implements a function to check if each query in a list of queries matches a given camel case pattern.
Time Complexity
The time complexity of the function is determined as follows:
- The
check
function goes through each character in the query strings
and the pattern stringt
at most once. The inner while loop runs as long as there are lowercase characters ins
that are not int
, and the outer while loop runs as long as there are characters int
. - In the worst case, each character of the query string will be checked exactly once against the pattern. This results in a linear complexity in terms of the length of the query string.
- The
check
function is called once for each query in thequeries
list.
If the average length of the queries is m
and the length of the pattern is n
, and there are k
queries, then the time complexity is O(k * (m + n))
, since for every query we have a separate traversal through the pattern string and the query string.
Space Complexity
The space complexity of the function is considered as follows:
- The
check
function uses a constant amount of extra space since it only uses a few integer variables to keep track of the indices. - The output list has the same length as the number of queries. This is where the space is used. However, this is not counted towards the extra space complexity as this is required for the output of the function.
So, the space complexity of the function is O(1)
(constant space complexity) for the auxiliary space.
Learn more about how to find time and space complexity quickly using problem constraints.
What are the most two important steps in writing a depth first search function? (Select 2)
Recommended Readings
Trie Introduction Imagine you have a magic dictionary where as soon as you start spelling a word it immediately tells you how many words that start with those letters How cool would that be This is exactly the kind of magic a data structure called trie performs What's a Trie
Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers div class responsive iframe iframe src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe div Two pointers is a common interview
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we