Problem Description
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.
Key Insights
- A query matches the pattern if we can find the characters of the pattern in the query in the same order.
- We can use a two-pointer technique to traverse both the pattern and the query strings.
- The pattern's characters must match the uppercase characters in the query in the same sequence.
Space and Time Complexity
Time Complexity: O(n * m), where n is the number of queries and m is the average length of the queries.
Space Complexity: O(1), as we are using a constant amount of extra space.
Solution
The solution involves using a two-pointer approach. We will iterate through each query and the pattern simultaneously using two pointers. For each query, we will check if we can match the pattern by moving through the query while ensuring that the characters of the pattern appear in the correct order. If we reach the end of the pattern, it means the query matches the pattern.