Find Anagram Substrings with Wildcard
In Uber's ride-hailing platform, ensuring data consistency and efficient search is crucial. Imagine a scenario where we need to identify specific patterns in driver or rider profiles, but with some flexibility. This problem asks you to find all occurrences of a pattern (which can include a wildcard) as an anagram within a larger text, mimicking a real-world need for flexible pattern matching.
Your task is to implement a function findAnagramSubstrings that takes two strings: text and pattern. The pattern string may contain a special wildcard character ?. This wildcard matches any single character. You need to find all starting indices in the text where a substring of text is an anagram of the pattern, considering the wildcard.
Specifically:
text is considered an anagram of pattern if it has the same length as pattern.c in pattern, its frequency in the substring must be at least its frequency in the pattern.? wildcard in pattern means that its corresponding position in the substring can be filled by any character. The total number of characters in the substring that are not explicitly required by the non-wildcard characters in pattern (i.e., excess characters beyond the minimum required counts) must exactly match the total number of ? wildcards in the pattern.Function Signature:
function findAnagramSubstrings(text: string, pattern: string): number[]
Parameters:
text: A string representing the main text to search within. It consists only of lowercase English letters ('a'-'z').pattern: A string representing the pattern to find anagrams of. It consists only of lowercase English letters ('a'-'z') and the wildcard character '?'.Return Value:
text where an anagram of pattern is found. The array should be sorted in ascending order.? can only appear in the pattern string, not in text.pattern.length is greater than text.length, no matches are possible, and an empty array should be returned.Examples
Example 1
Input:
text = "cbaebabacd", pattern = "abc"
Output:
[0,6]
Note:
The substring at index 0 is "cba", which is an anagram of "abc". The substring at index 6 is "bac", which is an anagram of "abc".
Example 2
Input:
text = "abaacb", pattern = "a?b"
Output:
[0,1,3]
Note:
Pattern "a?b" means we need one 'a', one 'b', and one wildcard character.
Example 3
Input:
text = "zzza", pattern = "???"
Output:
[0,1]
Note:
Pattern "???" means any 3 characters. All characters are matched by wildcards.
Constraints
1 <= text.length <= 10^51 <= pattern.length <= 10^5pattern.length <= text.lengthtext consists only of lowercase English letters ('a'-'z')pattern consists only of lowercase English letters ('a'-'z') and the wildcard character '?'Loading editor...