The problem
A pattern can have blanks, written ?, that match any one letter. Return every place i where the pattern fits the text: text[i + j] == pat[j] for every j where pat[j] is not ?. List the places in increasing order. Places may overlap, and the pattern must fit inside the text.
find_all("abcabcab", "cab") # [2, 5]
find_all("banana", "?an") # [0, 2]
find_all("aaaa", "aa") # [0, 1, 2]
find_all("ab", "abc") # []
The text has lower-case letters, and may also contain ?; only a ? in the pattern is a blank. The pattern has at least one character.
Limits
- The text has up to 20,000 letters and the pattern up to 20. The naive method of lesson 1 is fast enough.
Builds on STRG-1 Naive matching.
Continue on a laptop
Practice runs Python in the browser and needs a keyboard and a wider screen. Read the problem and open hints here, then write your solution on a laptop. Progress is saved per browser for now, so hints opened here stay on this device.
Need a hint?0 of 3 opened
- Hint 1Nudge
- Hint 2Approach Open hint 1 first
- Hint 3Pseudocode Open hint 2 first
- Worked solutionlast resort Opens after all 3 hints
Ctrl + Enter runs the tests. Tab indents; press Esc, then Tab, to leave the editor.
| # | Test | Result | Reads · time |
|---|---|---|---|
| 1 | The example | Not run | |
| 2 | A blank | Not run | |
| 3 | Overlapping places | Not run | |
| 4 | Only blanks | Not run | |
| 5 | Pattern longer than the text | Not run | |
| 6 | The last place | Not run | |
| 7 | The whole text | Not run | |
| 8 | A blank at each end | Not run | |
| 9 | No match | Not run | |
| 10 | A question mark is not a letter | Not run | |
| 11 | 20,000 letters | Not run | |
| 12 | Nearly every place | Not run |