Camelcase Matching

Medium

Asked by:

16 views

Topics:

ArraysStringsTwo Pointers

Given an array of strings queries and a string pattern, return a boolean array answer where answer[i] is true if queries[i] matches pattern, and false otherwise.

A query word queries[i] matches pattern if you can insert lowercase English letters into the pattern so that it equals the query. You may insert a character at any position in pattern or you may choose not to insert any characters at all.

Example 1:

Input: queries = ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"], pattern = "FB"
Output: [true,false,true,true,false]
Explanation: "FooBar" can be generated like this "F" + "oo" + "B" + "ar".
"FootBall" can be generated like this "F" + "oot" + "B" + "all".
"FrameBuffer" can be generated like this "F" + "rame" + "B" + "uffer".

Example 2:

Input: queries = ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"], pattern = "FoBa"
Output: [true,false,true,false,false]
Explanation: "FooBar" can be generated like this "Fo" + "o" + "Ba" + "r".
"FootBall" can be generated like this "Fo" + "ot" + "Ba" + "ll".

Example 3:

Input: queries = ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"], pattern = "FoBaT"
Output: [false,true,false,false,false]
Explanation: "FooBarTest" can be generated like this "Fo" + "o" + "Ba" + "r" + "T" + "est".

Constraints:

1 <= pattern.length, queries.length <= 100
1 <= queries[i].length <= 100
queries[i] and pattern consist of English letters.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Are the query strings guaranteed to be valid camel case (i.e., always start with a lowercase letter, and uppercase letters only delineate words)?
If a query string matches multiple patterns, should I return true even if it only partially matches another query string?
Are the query strings and patterns case-sensitive, or should I perform a case-insensitive match?
What should I return if the `queries` array is empty or null? Should I return an empty boolean array or throw an exception?
Can the patterns themselves contain uppercase characters that don't match in order? For example, if the pattern is 'FoBa' and the query is 'FooBar', should that be considered a match?

Brute Force Solution

Approach

The brute force strategy is like trying to spell a word using letter tiles where you are given a set of possible words. You try every possible combination of the words to see if you can form the intended word. You can think of this like the children's toy 'Bananagrams'.

Here's how the algorithm would work step-by-step:

For each possible word, see if it starts the target word.
If it does, check if the remaining part of the target word can be formed by the remaining words.
If it doesn't start the target word, move on to the next possible word.
Keep trying all possible combinations of words until the entire target word has been matched, or until we have exhausted all possibilities.
If at any point, there are no possible matching words to continue spelling the target word, we have failed, and we can move on to the next possible starting word and repeat the entire procedure.
If a combination matches the target word, mark that combination as a success.
After checking all combinations, we know exactly which patterns match the target word, and can report those successes.

Code Implementation

def camel_case_matching_brute_force(queries, pattern):
    results = []
    for query in queries:
        results.append(is_match_brute_force(query, pattern))
    return results

def is_match_brute_force(query, pattern):
    query_index = 0
    pattern_index = 0

    while query_index < len(query) and pattern_index < len(pattern):
        if query[query_index] == pattern[pattern_index]:
            query_index += 1
            pattern_index += 1
        elif query[query_index].isupper():
            # If uppercase but doesn't match, this fails
            return False

        else:
            query_index += 1

    # If the pattern is not fully consumed, it is not a match.
    if pattern_index != len(pattern):
        return False

    # Checking if rest of the query string contains uppercase chars.
    while query_index < len(query):
        if query[query_index].isupper():
            return False

        query_index += 1

    return True

Big(O) Analysis

Time Complexity

O(N * 2^M) – Let N be the number of query strings and M be the maximum length of a query string. For each query string, the algorithm explores all possible subsequences by recursively checking if characters from the pattern match the uppercase characters in the query. In the worst-case scenario, each character in a query string has two choices: either it matches the next character in the pattern or it doesn't. Thus, each query string can generate up to 2^M branches in the recursion tree. Since we iterate through N query strings, the overall time complexity becomes O(N * 2^M).

Space Complexity

O(N) – The brute force strategy described involves recursion to check all possible combinations of words. In the worst-case scenario, the depth of the recursion could be proportional to the length of the target word, which we can denote as N. Each recursive call consumes stack space to store function arguments and local variables. Therefore, the auxiliary space used by the recursion stack can grow up to O(N), where N represents the length of the target word.

Optimal Solution

Approach

The goal is to check if a query string can be formed by characters in a pattern string, with extra lowercase characters possibly present in the pattern. The key is to walk through both strings, matching uppercase characters carefully. Mismatches of uppercase letters mean the pattern doesn't match the query.

Here's how the algorithm would work step-by-step:

Go through the query and the pattern one character at a time, from left to right.
If the current characters in both strings are the same, move to the next character in both.
If the current character in the query is uppercase, but it doesn't match the current character in the pattern, the pattern doesn't match the query, so stop.
If the current character in the query is lowercase, simply move to the next character in the query.
If you reach the end of the pattern but not the end of the query, the pattern matches as long as the remaining characters in the query are lowercase.
If you reach the end of both the query and the pattern at the same time, the pattern matches the query.
By checking only the necessary uppercase letters, you avoid exploring incorrect paths and can quickly determine if a query matches.

Code Implementation

def camel_case_matching(queries, pattern):
    results = []
    for query in queries:
        pattern_index = 0
        query_index = 0
        matched = True

        while query_index < len(query):
            if pattern_index < len(pattern) and \
               query[query_index] == pattern[pattern_index]:
                pattern_index += 1
                query_index += 1
            elif query[query_index].isupper():
                # Uppercase mismatch means no match
                matched = False
                break

            else:
                query_index += 1

        # Check remaining query characters
        if matched and pattern_index < len(pattern):
            matched = False

        results.append(matched)

    return results

Big(O) Analysis

Time Complexity

O(N+M) – The algorithm iterates through the query string of length N and the pattern string of length M once. The core logic involves comparing characters in these two strings sequentially. Therefore, the time complexity is directly proportional to the sum of the lengths of the two input strings. This results in a linear time complexity expressed as O(N+M).

Space Complexity

O(1) – The algorithm iterates through the query and pattern strings using index variables. No auxiliary data structures like lists, hash maps, or recursion are employed to store intermediate results or visited states. The memory footprint remains constant, irrespective of the query and pattern string lengths, where N could represent the maximum length between the query and the pattern. Therefore, the space complexity is O(1).

Edge Cases

Case	How to Handle
queries or pattern is null or empty	Return an empty list if either queries or pattern is null or empty to avoid null pointer exceptions and handle invalid inputs.
pattern is longer than any query string	Return false immediately for that query as a camelCase subsequence cannot be longer than the string itself.
query string is empty but pattern is not	Return false since the query cannot match a non-empty pattern.
pattern contains uppercase characters that are not present in query string	The solution should correctly identify the mismatch and return false.
query string contains extra uppercase characters that are not part of the pattern	The solution should still return true if the pattern is a subsequence of the uppercase characters in the query.
Pattern matches a prefix of the query but not the entire uppercase subsequence	The solution needs to ensure all uppercase characters of the pattern are found and in the correct order within the query's uppercase subsequence.
Extremely long query strings	Ensure the algorithm's time complexity remains linear with respect to query length to avoid performance issues.
Pattern is a single uppercase character	This should be handled correctly by the subsequence matching logic, ensuring at least one uppercase character is in the query.

queries or pattern is null or empty

How to Handle:

Return an empty list if either queries or pattern is null or empty to avoid null pointer exceptions and handle invalid inputs.

pattern is longer than any query string

How to Handle:

Return false immediately for that query as a camelCase subsequence cannot be longer than the string itself.

query string is empty but pattern is not

How to Handle:

Return false since the query cannot match a non-empty pattern.

pattern contains uppercase characters that are not present in query string

How to Handle:

The solution should correctly identify the mismatch and return false.

query string contains extra uppercase characters that are not part of the pattern

How to Handle:

The solution should still return true if the pattern is a subsequence of the uppercase characters in the query.

Pattern matches a prefix of the query but not the entire uppercase subsequence

How to Handle:

The solution needs to ensure all uppercase characters of the pattern are found and in the correct order within the query's uppercase subsequence.

Extremely long query strings

How to Handle:

Ensure the algorithm's time complexity remains linear with respect to query length to avoid performance issues.

Pattern is a single uppercase character

How to Handle:

This should be handled correctly by the subsequence matching logic, ensuring at least one uppercase character is in the query.