<div>
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:
<pre>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. </pre>
Example 2:
<pre>Input: s = "zzzzzyyyyy", words = ["zzyy","zy","zyy"] Output: 3 </pre>
Constraints:
1 <= s.length, words.length <= 1001 <= words[i].length <= 100sandwords[i]consist of lowercase letters.
</div>
题目大意：
Cisco常考题
定义了一种富于表现力的单词，就是说某个字母可以重复三次或以上，叫stretchy
找给定的单词列表中的单词可以成为stretchy单词的个数
解题思路：
统计每个字符的个数，然后比较对应每个字符个数
解题步骤：
N/A
注意事项：
- Line 13的条件，若个数不等，word的字符个数大于stretchy的字符个数(word不能删除字符)，或者stretchy的个数小于3，就不满足
Python代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27def expressiveWords(self, s: str, words: List[str]) -> int:
res = 0
s_count = self.get_consecutive_count(s)
for word in words:
char_count = self.get_consecutive_count(word)
if len(char_count) != len(s_count):
continue
for i in range(len(s_count)):
char_s, count_s = s_count[i]
char_w, count_w = char_count[i]
if char_w != char_s:
break
if count_s != count_w and (count_w > count_s or count_s < 3): # remember
break
if i == len(s_count) - 1:
res += 1
return res
def get_consecutive_count(self, s):
s += ' '
s_count, count = [], 1
for i in range(1, len(s)):
if s[i] != s[i - 1]:
s_count.append((s[i - 1], count))
count = 0
count += 1
return s_count
算法分析：
时间复杂度为O(n)，空间复杂度O(1)
