← 返回 google 的题目列表Stuck Keyboard / Jammed String Dictionary Match
类型:online_judge
Problem: Stuck Keyboard (Jammed String) Dictionary Matching
You are given a word list dictionary and an input string jammed_string.
Assume the keyboard is “stuck”. When typing a dictionary word:
No characters are deleted.
The order of characters is preserved.
No new different characters are inserted.
Any character may be repeated multiple times consecutively (i.e., each character c in the original word can become c repeated k times in the output, for any k >= 1).
Return all words in dictionary that could have produced jammed_string.
Examples
help -> hellp is possible
hello -> hheellllo is possible
banana -> baanaaannnaaa is possible
I/O
Input: dictionary, jammed_string
Output: list of all matching dictionary words (any order)
Sample tests
dictionary = ["help","hello","banana"], jammed_string = "hellp" → output includes "help"
dictionary = ["hello","help"], jammed_string = "hheellllo" → output includes "hello"
dictionary = ["banana","band"], jammed_string = "baanaaannnaaa" → output includes "banana"
dictionary = ["abc","ab"], jammed_string = "aabbcc" → output includes "abc"
dictionary = ["abc"], jammed_string = "abdc" → output is empty
Example
Input
3
help
hello
banana
hellp
Output
help