Glide Typing Matches
MediumStrings · SalesForce
On a glide-typing keyboard the user drags a finger across the keys, and the keyboard records every letter passed over as the string path. A dictionary word can be typed by that path when all of the following hold:
- The word's first letter equals the first letter of
path. - The word's last letter equals the last letter of
path. - The word is a subsequence of
path: its letters can be found inpathin the same order, not necessarily next to each other, and each character ofpathcan be used for at most one letter of the word.
Given path and a list words, return every word that can be typed, without duplicates, sorted in ascending lexicographic order. Return an empty list if none can be typed.
path and the word list can both be large, so scanning the entire path for every word may be too slow.
Example 1
- Input:
- path = "hgferdsaplkjo", words = ["hello", "hero", "help", "halo", "hero", "ho", "hop"]
- Output:
- ["halo", "hero", "ho"]
- Explanation
hero,haloandhostart withh, end witho, and their letters appear in order along the path.helloneeds twolcharacters but the path has one;helpandhopdo not end witho. The duplicateherois reported once.
Example 2
- Input:
- path = "cvbnmjhyt", words = ["cat", "cmt", "cnyt", "cyht"]
- Output:
- ["cmt", "cnyt"]
- Explanation
catfails because the path has noa.cyhtfails becausehcomes beforeyon the path, so the letters are not in order.
Example 3
- Input:
- path = "aba", words = ["a", "aa", "aba", "aaa"]
- Output:
- ["a", "aa", "aba"]
- Explanation
- A one-letter word only needs its letter to be both the first and last character of the path.
aaaneeds threeacharacters but the path only has two.
Constraints
1 <= path.length <= 10^51 <= words.length <= 10^41 <= words[i].length <= 50pathand all words consist of lowercase English letters