Problem Description

You are given an array of strings queries and a string pattern. Your task is to determine which query strings match the pattern according to specific rules.

A query string matches the pattern if you can transform the pattern into the query by inserting lowercase English letters at any positions (including at the beginning, end, or between characters). You can choose to insert no characters at all if the pattern already matches the query.

The key rules are:

• You can only insert lowercase letters into the pattern
• You cannot remove or rearrange characters from the pattern
• All characters from the pattern must appear in the same order in the query
• Any uppercase letters in the query must match exactly with the pattern

For example:

• If pattern = "FB" and query = "FooBar", this matches because we can insert lowercase letters "oo" and "ar" to transform "FB" into "FooBar"
• If pattern = "FB" and query = "FooBarTest", this doesn't match because "Test" contains an uppercase 'T' that's not in the pattern
• If pattern = "FB" and query = "Foo", this doesn't match because 'B' from the pattern is missing

Return a boolean array answer where answer[i] is true if queries[i] matches the pattern, and false otherwise.

Intuition

The problem is essentially asking us to check if we can match a pattern string with a query string by only adding lowercase letters to the pattern. This immediately suggests a two-pointer approach where we try to match characters from both strings.

Let's think about what makes a valid match:

1. Every character in the pattern must appear in the query in the same order
2. Between pattern characters, we can only have lowercase letters in the query
3. Any uppercase letter in the query that's not in the pattern makes it invalid

This leads us to a greedy matching strategy: for each character in the pattern, we try to find it in the query while skipping only lowercase letters. If we encounter an uppercase letter that doesn't match the current pattern character, we know it's impossible to match.

The key insight is that uppercase letters act as "anchors" - they must match exactly with the pattern, while lowercase letters are flexible and can be inserted anywhere. So our algorithm becomes:

• Try to match each pattern character with the query
• While searching for a match, skip lowercase letters (these are the "inserted" characters)
• If we hit an uppercase letter that doesn't match, fail immediately
• After matching all pattern characters, ensure any remaining characters in the query are lowercase

This greedy approach works because we're only allowed to insert characters, not remove or rearrange them. So the first occurrence of each pattern character in the query (following the rules) is the only valid match position.

Learn more about Trie and Two Pointers patterns.

Solution Approach

The solution uses a two-pointer technique to check if each query matches the pattern. We implement a helper function check(s, t) where s is the query string and t is the pattern.

Here's how the algorithm works:

1. Initialize two pointers: Set i = 0 for traversing the query string s and j = 0 for traversing the pattern t. Also get the lengths m = len(s) and n = len(t).

2. Match pattern characters: While j < n (still have pattern characters to match):

   • Skip lowercase letters in the query: Use a while loop to advance i as long as s[i] is a lowercase letter and doesn't match t[j]
   • Check for match: If we've reached the end of s (i == m) or the characters don't match (s[i] != t[j]), return False
   • If characters match, advance both pointers: i += 1 and j += 1

3. Handle remaining query characters: After matching all pattern characters, we need to ensure any remaining characters in the query are lowercase:

   • Use another while loop to skip lowercase letters: while i < m and s[i].islower(): i += 1
   • Return True if we've consumed the entire query (i == m), otherwise False

4. Process all queries: Apply the check function to each query in the list using a list comprehension: [check(q, pattern) for q in queries]

The time complexity is O(n × m) where n is the total number of characters across all queries and m is the length of the pattern. For each query, we potentially scan through all its characters once.

The space complexity is O(1) for the checking function itself (only using pointers), though the output array takes O(k) space where k is the number of queries.

Example Walkthrough

Let's walk through the solution with pattern = "FB" and query = "FooBar".

Step 1: Initialize pointers

• i = 0 (pointing to 'F' in "FooBar")
• j = 0 (pointing to 'F' in "FB")
• m = 6 (length of "FooBar")
• n = 2 (length of "FB")

Step 2: Match first pattern character 'F'

• While j < 2 (true, j=0):
  • Check if we need to skip lowercase letters: s[0] is 'F' (uppercase), so no skipping needed
  • Check match: s[0] = 'F' equals t[0] = 'F' ✓
  • Advance both pointers: i = 1, j = 1

Step 3: Match second pattern character 'B'

• While j < 2 (true, j=1):
  • Skip lowercase letters:
    • s[1] = 'o' is lowercase and doesn't equal 'B', so i = 2
    • s[2] = 'o' is lowercase and doesn't equal 'B', so i = 3
    • s[3] = 'B' is uppercase, stop skipping
  • Check match: s[3] = 'B' equals t[1] = 'B' ✓
  • Advance both pointers: i = 4, j = 2

Step 4: Check remaining characters

• Now j = 2, so we've matched all pattern characters
• Check remaining query characters (indices 4-5):
  • s[4] = 'a' is lowercase, skip: i = 5
  • s[5] = 'r' is lowercase, skip: i = 6
• We've reached the end (i = 6 = m)
• Return True ✓

The query "FooBar" matches pattern "FB" because we successfully matched all pattern characters in order ('F' and 'B') while only encountering lowercase letters ('o', 'o', 'a', 'r') in between, which represent our valid insertions.

Solution Implementation

Time and Space Complexity

Time Complexity: O(k * (m + n)), where k is the number of queries, m is the average length of each query string, and n is the length of the pattern string.

• The outer list comprehension iterates through all k queries
• For each query, the check function is called, which uses two pointers to traverse through the query string and pattern
• In the worst case, the first while loop iterates through all characters in both the query string (m) and pattern (n)
• The second while loop after pattern matching may iterate through remaining lowercase characters in the query string, but this is still bounded by m
• Therefore, for each query, the time complexity is O(m + n)
• Total time complexity: O(k * (m + n))

Space Complexity: O(k), where k is the number of queries.

• The check function uses only a constant amount of extra space with variables m, n, i, and j
• The main space consumption comes from the output list that stores k boolean results
• The list comprehension creates a new list of size k to store the results
• No recursive calls or additional data structures are used that scale with input size
• Therefore, the space complexity is O(k)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Handling of Uppercase Letters in the Query

The Pitfall: A common mistake is not properly validating that uppercase letters appearing in the query but not in the pattern should cause a mismatch. The algorithm might incorrectly skip over uppercase letters thinking they're optional like lowercase letters.

Example of the Bug:

# Incorrect implementation that treats uppercase letters like lowercase
while query_idx < query_len and query[query_idx] != pattern[pattern_idx]:
    query_idx += 1  # Wrong! This skips ANY character, including uppercase

The Problem: With pattern = "FB" and query = "FooTBar", this buggy code would incorrectly return True because it skips the uppercase 'T' that isn't in the pattern.

The Solution: Always check if the character is lowercase before skipping:

# Correct implementation
while query_idx < query_len and query[query_idx] != pattern[pattern_idx] and query[query_idx].islower():
    query_idx += 1  # Only skip lowercase letters

2. Forgetting to Validate Remaining Characters After Pattern Match

The Pitfall: After successfully matching all pattern characters, forgetting to check that any remaining characters in the query are only lowercase letters.

Example of the Bug:

def is_match(query, pattern):
    # ... matching logic ...
  
    # Bug: Immediately return True after matching pattern
    return pattern_idx == pattern_len  # Wrong! Doesn't check remaining query characters

The Problem: With pattern = "FB" and query = "FooBarTest", this would incorrectly return True even though "Test" contains an uppercase 'T' not in the pattern.

The Solution: Always validate the remaining query characters:

# After matching all pattern characters
while query_idx < query_len and query[query_idx].islower():
    query_idx += 1

return query_idx == query_len  # Ensures all remaining characters were lowercase

3. Edge Case: Empty Pattern

The Pitfall: Not handling the case where the pattern is empty, which should only match queries containing all lowercase letters.

The Solution: The current implementation handles this correctly because when pattern_len = 0, the first while loop is skipped entirely, and the second while loop validates that all query characters are lowercase. However, it's worth being aware of this edge case during testing.

Test Cases to Verify:

• pattern = "", query = "abc" → True
• pattern = "", query = "Abc" → False
• pattern = "", query = "" → True