LeetCode 809 Expressive Words

LeetCode

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". If s = "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 <= 100
1 <= words[i].length <= 100 s and words[i] consist of lowercase letters.

题目大意：

Cisco常考题
定义了一种富于表现力的单词，就是说某个字母可以重复三次或以上，叫stretchy
找给定的单词列表中的单词可以成为stretchy单词的个数

解题思路：

统计每个字符的个数，然后比较对应每个字符个数

解题步骤：

N/A

注意事项：

1. Line 13的条件，若个数不等，word的字符个数大于stretchy的字符个数(word不能删除字符)，或者stretchy的个数小于3，就不满足

Python代码：

def 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)