Loading page…
Practice problem · easy
A search box in a notes app finds a saved shortcut by its name. Some keyboards are sticky: a key that is held down types its letter again and again.
Before the app says "no match", it checks whether the typed text could be the saved name with some keys held. You are asked to write that check.
Write could_be_sticky(name, typed).
name is the saved shortcut name. typed is the text in the search box. Both use only lowercase letters.typed could come from name if you can type each letter of name, in order, one or more times, and nothing else.true if typed could be name with some keys held, and false if not.Input: name = "alex", typed = "aaleex"
Output: truePointer i reads name and pointer j reads typed. Each typed letter is either the next letter of the name or a repeat of the letter typed right before it.
| i | j | Typed letter | Next name letter | Move |
|---|---|---|---|---|
| 0 | 0 | a | a | it matches: i becomes 1, j becomes 1 |
| 1 | 1 | a | l | no match, but it repeats the typed a: j becomes 2 |
| 1 | 2 | l | l | it matches: i becomes 2, j becomes 3 |
| 2 | 3 | e | e | it matches: i becomes 3, j becomes 4 |
| 3 | 4 | e | x | no match, but it repeats the typed e: j becomes 5 |
| 3 | 5 | x | x | it matches: i becomes 4, j becomes 6 |
Typed is used up and all four letters of the name are used. The answer is true.
Input: name = "saeed", typed = "ssaaedd"
Output: falseThe name has two e's in a row, but the typed text has only one.
Input: name = "alex", typed = "alexxr"
Output: falseThe last letter r is not a repeat of the letter before it, and no letters of the name are left to match it.
1 ≤ name.length ≤ 100,000 (letters in the saved name)1 ≤ typed.length ≤ 100,000 (letters in the search box)a to zThe first attempt tries both choices at every typed letter and never remembers where it has been. When the typed text is one repeated letter, each letter gives two choices, and the paths multiply. At 100,000 letters it never finishes.
A walk that reads each text once takes at most 200,000 steps.
could_be_sticky · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.