We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Camelcase Matching

Number: 1080

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given an array of query strings and a pattern string, determine for each query whether it is possible to form the query by inserting lowercase letters into the pattern without changing the order of the pattern's characters. In other words, the query must contain all characters of the pattern in order, and any extra characters inserted must be lowercase.

Key Insights

  • Use two pointers: one for iterating over the query and one for the pattern.
  • The characters in the pattern must appear in the query in the same order.
  • Any extra characters in the query that do not match the pattern must be lowercase.
  • If an uppercase letter appears in the query and it is not expected by the pattern, the query does not match.

Space and Time Complexity

Time Complexity: O(n * m) where n is the number of queries and m is the maximum length of a query. Space Complexity: O(1) extra space, aside from the output array.

Solution

For each query, iterate through each character using a pointer for the query and another pointer for the pattern. When a character in the query matches the current character of the pattern, move the pattern pointer forward. If the character does not match, it must be a lowercase letter; otherwise, the query fails the match. Once finished, ensure that all characters of the pattern have been matched and that any remaining characters in the query are lowercase. This two-pointer approach guarantees that the pattern's order is respected while allowing insertions.

Code Solutions

# Python solution for Camelcase Matching

def camelMatch(queries, pattern):
    # Helper function to check if a single query matches the pattern
    def matches(query):
        pattern_index = 0
        # Iterate over every character in the query string
        for char in query:
            # If there is a character in pattern and it matches the query character, move to the next pattern character
            if pattern_index < len(pattern) and char == pattern[pattern_index]:
                pattern_index += 1
            # Else if the character is uppercase and doesn't match the current pattern character, fail the match
            elif char.isupper():
                return False
        # Check if we have exhausted the pattern
        return pattern_index == len(pattern)
    
    # Build the result list by checking each query
    return [matches(query) for query in queries]

# Example usage:
queries = ["FooBar", "FooBarTest", "FootBall", "FrameBuffer", "ForceFeedBack"]
pattern = "FB"
print(camelMatch(queries, pattern))  # Expected output: [True, False, True, True, False]
← Back to All Questions