1023. Camelcase Matching

MediumTrieTwo PointersStringString Matching
Leetcode Link

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:

  1. The characters in both queries[i] and pattern must match in order, and the matching characters in queries[i] must be in the same positions as in pattern. 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.
  2. 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 and j, to traverse queries[i] and pattern, respectively.
  • Iterate over queries[i] with pointer i, and for each character, check if it matches the jth character of pattern.
  • If the characters match, move both pointers forward.
  • If the characters do not match, and the ith character of queries[i] is lowercase, we can attempt to skip it by moving pointer i 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 in queries[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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

The three-steps of Depth First Search are:

  1. Identify states;
  2. Draw the state-space tree;
  3. DFS on the state-space tree.

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:

  1. Initialize two pointers: i starts at the beginning of s while j starts at the beginning of t.
  2. Iterate through s using the pointer i:
    • If s[i] is a lowercase letter that does not match t[j], increment i to skip it. This step embodies the rule that allows the insertion of lowercase letters.
    • If s[i] matches t[j], increment both pointers i and j to check the next characters since a match dictates we move in both queries and pattern.
    • If the characters do not match and s[i] is not a lowercase letter, return false as we can't insert uppercase letters or skip non-matching uppercase letters.
  3. Once j has reached the end of t, we check the remainder of s to ensure all leftover characters are lowercase. If we encounter an uppercase letter or i hasn't yet reached the end of s, we return false as the additional characters can't be part of the pattern.
  4. If i has reached the end of s, we return true, 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:

  1. Use a list comprehension to iterate over all query strings in queries.
  2. For each query, call the check function with the query and the pattern.
  3. 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following problems can be solved with backtracking (select multiple)

Example 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:

  1. "After":

    • Initialize pointers i=0 and j=0. Since queries[i] = 'A' and pattern[j] = 'A', they match, and we increment both pointers.
    • Now i=1 and j=1, and we have queries[i] = 'f' and pattern[j] = 'F'. They do not match because one is lowercase and the other is uppercase, but since queries[i] is lowercase, we can skip it by incrementing i.
    • With i=2 and j=1, we now have queries[i] = 't' and pattern[j] = 'F'. The letters do not match, so we increment i as 't' is lowercase.
    • At i=3, j=1, we have queries[i] = 'e', still lowercase. We skip it.
    • Now i=4, j=1, and queries[i] = 'r'. Another lowercase to skip.
    • Since j has not moved and i reached the end of queries[i] without matching 'F' from pattern, we return false.
  2. "AFter":

    • We set i=0 and j=0. They match ('A' with 'A'), so both pointers increment.
    • At i=1, j=1, queries[i] = 'F' and pattern[j] = 'F', they match, so increment both pointers again.
    • Now i=2, and since j has reached the end of pattern, we only need to check that the remaining characters in queries[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 of s, and j has reached the end of t, we return true.
  3. "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 remaining queries[i], we return true.
  4. "BFilter":

    • Start with i=0 and j=0. We find that 'B' doesn't match 'A' in pattern 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.

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.

Not Sure What to Study? Take the 2-min Quiz:

What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?

Python Solution

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

Java Solution

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

C++ Solution

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

Typescript Solution

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
Fast Track Your Learning with Our Quick Skills Quiz:

How does merge sort divide the problem into subproblems?

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 string s and the pattern string t at most once. The inner while loop runs as long as there are lowercase characters in s that are not in t, and the outer while loop runs as long as there are characters in t.
  • 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 the queries 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.


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫