1200. Joker Pattern Hits
A word-game solver searches a string of tiles for a template. The template pattern may contain the joker character '?', which stands for any single letter, while every other character must match exactly. The tiles are in the lowercase string s.
Return every start index i (0-based) such that s[i..i+m) matches pattern, where m is the pattern length, in ascending order. Matches may overlap. If there is no match, return an empty array. A direct check of every start position is the intended approach.
Constraints: 1 <= pattern.length <= s.length <= 1000, s contains only lowercase letters, and pattern contains lowercase letters and '?'. Brute force runs in O(n*m) time with O(1) extra space besides the answer.
Example 1
- Input:
- s = "abcabc", pattern = "a?c"
- Output:
- [0,3]
- Explanation:
The pattern matches at index 0 (abc) and index 3 (abc).
Example 2
- Input:
- s = "aaaa", pattern = "aa"
- Output:
- [0,1,2]
- Explanation:
Overlapping matches count, so the pattern starts at indices 0, 1 and 2.
Example 3
- Input:
- s = "xyz", pattern = "b"
- Output:
- []
- Explanation:
The letter b never occurs, so the answer is empty.
Constraints
1 ≤ pattern.length ≤ s.length ≤ 1000
s is lowercase
pattern is lowercase letters and '?'
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n*m)
- Space
- O(1)