Description
Sometimes people repeat letters to represent extra feeling. For example:
"hello" -> "heeellooo""hi" -> "hiiii"
In these strings like "heeellooo", we have groups of adjacent letters that are all the same: "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 made to be equal to s by any number of applications of the following extension operation: choose a group consisting of characters c, and add some number of characters c to the group so that the size of the group is three or more.
- For example, starting with
"hello", we could do an extension on the group"o"to get"hellooo", but we cannot get"helloo"since the group"oo"has a size less than three. Also, we could do another extension like"ll" -> "lllll"to get"helllllooo". Ifs = "helllllooo", then the query word"hello"would be stretchy because of these two extension operations:query = "hello" -> "hellooo" -> "helllllooo" = s.
Return the number of query strings that are stretchy.
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
Constraints:
1 <= s.length, words.length <= 1001 <= words[i].length <= 100sandwords[i]consist of lowercase letters.
Solutions
Solution 1: Traversal Counting + Two Pointers
We can traverse the array words, and for each word t in the array, check if t can be expanded to obtain s. If it can, increment the answer by one.
Therefore, the key problem is to determine if the word t can be expanded to obtain s. We use a function check(s, t) to determine this. The implementation logic of the function is as follows:
First, check the length relationship between s and t. If the length of t is greater than s, return false directly. Otherwise, use two pointers i and j to point to s and t, respectively, both initially set to 0.
If the characters pointed to by i and j are different, then t cannot be expanded to obtain s, and we return false. Otherwise, we need to check the relationship between the consecutive occurrence counts of the characters pointed to by i and j, denoted as c_1 and c_2. If c_1 \lt c_2 or c_1 \lt 3 and c_1 ≠ c_2, then t cannot be expanded to obtain s, and we return false. Otherwise, move i and j to the right by c_1 and c_2 times, respectively, and continue checking.
If both i and j reach the end of the strings, then t can be expanded to obtain s, and we return true. Otherwise, we return false.
The time complexity is O(n × m + ∑_{i=0}^{m-1} w_i), where n and m are the lengths of the string s and the array words, respectively, and w_i is the length of the i-th word in the array words.
class Solution: def expressiveWords(self, s: str, words: List[str]) -> int: def check(s, t): m, n = len(s), len(t) if n > m: return False i = j = 0 while i < m and j < n: if s[i] != t[j]: return False k = i while k < m and s[k] == s[i]: k += 1 c1 = k - i i, k = k, j while k < n and t[k] == t[j]: k += 1 c2 = k - j j = k if c1 < c2 or (c1 < 3 and c1 != c2): return False return i == m and j == n return sum(check(s, t) for t in words)(code-box)
