#809

Expressive Words

specialist · 990 · lc medium +32 · verified · 46.7% accepted · 915 likes · top 31%

⚑ Fast & Slow Pointers (Floyd's Cycle)

Description

People sometimes stretch letters in words to convey extra emotion. For instance:

 - "hello" -> "heeellooo"

 - "hi" -> "hiiii"

In a stretched string like "heeellooo", consecutive identical letters form groups: "h", "eee", "ll", "ooo".

You are given a string s and an array of query strings words. A query word is stretchy if it can be transformed into s by any number of extension steps, where each step selects a run of identical characters and expands it to a length of at least three.

 - For example, beginning with "hello", extending the "o" run yields "hellooo" (valid, length >= 3), but "helloo" is not reachable this way because the resulting run has length 2. A further extension of "ll" -> "lllll" gives "helllllooo". If s = "helllllooo", then "hello" is stretchy via these two operations.

Return the count of stretchy query strings.

Example 1:

Input: s = "heeellooo", words = ["hello", "hi", "helo"]
Output: 1
Explanation:
We can extend "e" and "o" in the word "hello" to get "heeellooo".
We can't extend "helo" to get "heeellooo" because the group "ll" is not size 3 or more.

Example 2:

Input: s = "zzzzzyyyyy", words = ["zzyy","zy","zyy"]
Output: 3

Code

1
2
3