Find Dictionary Matches for a Jammed String

Problem Statement

You are given a "jammed" string where the user may have held down certain keys, resulting in consecutive repeated characters. You are also provided a dictionary of valid words. A word in the dictionary is a match if it can be transformed into the jammed string by expanding some of its characters (i.e., replacing a single character c with one or more instances of c).

For example, if the jammed string is "heeelllooo", then the dictionary word "hello" is a match. However, "helo" is not, because it lacks the necessary letters to form the clusters in the jammed string.

Implement the function find_matches(jammed_string, dictionary) which returns a list of all words from the dictionary that match the jammed input.

Function Signature

def find_matches(jammed_string: str, dictionary: list[str]) -> list[str]:

Constraints

• 1 <= len(jammed_string) <= 1000
• 1 <= len(dictionary) <= 5000
• Dictionary words consist of lowercase English letters.

Examples

Example 1

Input: jammed_string = "aaabbbccc" dictionary = ["abc", "aabbc", "aaabbccc"] Output: ["abc", "aaabbccc"] Explanation: "abc" can expand to "aaabbbccc". "aabbc" cannot because it has only two 'a's, but the input has three.

Example 2

Input: jammed_string = "heeello" dictionary = ["hello", "helo"] Output: ["hello"]

Edge Cases

• Empty jammed string or empty dictionary.
• Input contains characters not present in the dictionary words.
• Single character words or strings.