DIY: Expressive Words

Solve the interview question "Expressive Words" in this lesson.

Problem statement

Given a string, S, and a list of words, return the number of words that are stretchy.

A word in words is stretchy with respect to S if S can be derived by extending the letters of the word. Here is the extend rule:

For any group of the same continuous characters in a word from words, you can keep them as is, or you can extend them by the same characters so that the size of the extended group is >= 3.

For example, the groups of same continuous characters in word = ddiinnso are ["dd", "ii", "nn", "s", "o"]. Therefore, it is “strechy” with respect to S = dddiiiinnssssssoooo. In this instance, we can extend "dd"->"ddd", "ii"->"iiii", keep "nn" as it is, "s"->"ssssss", and "o"->"oooo".

Input

The input will be a string S and a list of words. The following is an example input:

S = "tttttllll"
words = ["tl","tll","ttll","ttl"]

Output

The output will be an integer value representing the number of stretchy words in words. The following is an example output for the above input:

4

All four words in words can be extended to obtain S.

Coding exercise

Implement the expressiveWords(S, words) function, where S is the string and words is the list of words. The function will return a single integer value representing the number of stretchy words in words.

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.