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". 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 <= 1001 <= words[i].length <= 100s and words[i] consist of lowercase letters.
Solutions#
Solution 1#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| 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)
|
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| class Solution {
public int expressiveWords(String s, String[] words) {
int ans = 0;
for (String t : words) {
if (check(s, t)) {
++ans;
}
}
return ans;
}
private boolean check(String s, String t) {
int m = s.length(), n = t.length();
if (n > m) {
return false;
}
int i = 0, j = 0;
while (i < m && j < n) {
if (s.charAt(i) != t.charAt(j)) {
return false;
}
int k = i;
while (k < m && s.charAt(k) == s.charAt(i)) {
++k;
}
int c1 = k - i;
i = k;
k = j;
while (k < n && t.charAt(k) == t.charAt(j)) {
++k;
}
int c2 = k - j;
j = k;
if (c1 < c2 || (c1 < 3 && c1 != c2)) {
return false;
}
}
return i == m && j == n;
}
}
|
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
| class Solution {
public:
int expressiveWords(string s, vector<string>& words) {
auto check = [](string& s, string& t) -> int {
int m = s.size(), n = t.size();
if (n > m) return 0;
int i = 0, j = 0;
while (i < m && j < n) {
if (s[i] != t[j]) return 0;
int k = i;
while (k < m && s[k] == s[i]) ++k;
int c1 = k - i;
i = k, k = j;
while (k < n && t[k] == t[j]) ++k;
int c2 = k - j;
j = k;
if (c1 < c2 || (c1 < 3 && c1 != c2)) return 0;
}
return i == m && j == n;
};
int ans = 0;
for (string& t : words) ans += check(s, t);
return ans;
}
};
|
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
27
28
29
30
31
32
33
34
35
| func expressiveWords(s string, words []string) (ans int) {
check := func(s, t string) bool {
m, n := len(s), len(t)
if n > m {
return false
}
i, j := 0, 0
for i < m && j < n {
if s[i] != t[j] {
return false
}
k := i
for k < m && s[k] == s[i] {
k++
}
c1 := k - i
i, k = k, j
for k < n && t[k] == t[j] {
k++
}
c2 := k - j
j = k
if c1 < c2 || (c1 != c2 && c1 < 3) {
return false
}
}
return i == m && j == n
}
for _, t := range words {
if check(s, t) {
ans++
}
}
return ans
}
|
