Algorithm
Problem Name: 809. Expressive Words
Problem Link: https://leetcode.com/problems/expressive-words/
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
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
int expressiveWords(string S, vector<string>& words) {
int res = 0;
vector < char>letter;
vector<int>count;
for(int i = 0, index = 0; i < S.size(); index++){
letter.push_back(S[i]);
count.push_back(1);
int j = i + 1;
while(j < S.size() && S[j] == S[i]) count[index]++, j++;
i = j;
}
for(auto s: words){
vector < char>v;
vector<int>c;
bool b = true;
int index = 0;
for(int i = 0; i < s.size(); index++){
v.push_back(s[i]);
c.push_back(1);
int j = i + 1;
while(j < s.size() && s[j] == s[i]) c[index]++, j++;
if(v[index] != letter[index] || (c[index] != count[index] && count[index] < 3> || c[index] > count[index]){
b = false;
break;
}
i = j;
}
if(b && index == count.size()) res++;
}
return res;
}
};
class Solution {
public:
int expressiveWords(string S, vector < string>& words) {
int res = 0;
for (auto& x: words) {
if (isValid(x, S)) {
++res;
}
}
return res;
}
bool isValid(string& x, string& y) {
if (x.size() > y.size()) {
return false;
}
int i = 0, j = 0, m = x.size(), n = y.size();
while (i < m) {
if (x[i] != y[j]) {
return false;
}
int count1 = 1, count2 = 1;
while (i + 1 < m && x[i] == x[i + 1]) {
++i;
++count1;
}
while(j + 1 < n && y[j] == y[j + 1]) {
++j;
++count2;
}
++i;
++j;
if (count1 == count2 || (count1 < count2 && count2 >= 3)) {
continue;
} else {
return false;
}
}
return i == m && j == n;
}
};
Input
s = "heeellooo", words = ["hello", "hi", "helo"]
Output
1
#2 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int expressiveWords(String s, String[] words) {
return (int) Arrays.stream(words).filter(word -> isExpressive(s, word)).count();
}
private boolean isExpressive(String s, String word) {
int sIdx = 0;
int wordIdx = 0;
while (sIdx < s.length() && wordIdx < word.length()) {
if (s.charAt(sIdx) != word.charAt(wordIdx)) {
return false;
}
char c1 = s.charAt(sIdx);
int countC1 = 0;
while (sIdx < s.length() && s.charAt(sIdx) == c1) {
sIdx++;
countC1++;
}
char c2 = word.charAt(wordIdx);
int countC2 = 0;
while (wordIdx < word.length() && word.charAt(wordIdx) == c2) {
wordIdx++;
countC2++;
}
if (countC1 == countC2 || (countC1 > countC2 && countC1 >= 3)) {
continue;
}
return false;
}
return sIdx == s.length() && wordIdx == word.length();
}
}
Input
s = "heeellooo", words = ["hello", "hi", "helo"]
Output
1
#3 Code Example with Python Programming
Code -
Python Programming
class Solution:
def expressiveWords(self, S, words):
if not S: return 0
guide, i, j, res = [], 0, 0, 0
while i < len(S):
while j + 1 Input
s = "zzzzzyyyyy", words = ["zzyy","zy","zyy"]
Output
3
#4 Code Example with C# Programming
Code -
C# Programming
using System.Collections.Generic;
namespace LeetCode
{
public class _0809_ExpressiveWords
{
public int ExpressiveWords(string S, string[] words)
{
(var keys, var counts) = CountString(S);
var result = 0;
foreach (var word in words)
{
(var wordKeys, var wordCounts) = CountString(word);
if (keys.Count != wordKeys.Count) continue;
var continueNext = false;
for (int i = 0; i < keys.Count; i++)
{
if (keys[i] != wordKeys[i] || counts[i] < wordCounts[i] || (counts[i] < 3 && counts[i] != wordCounts[i]))
{
continueNext = true;
break;
}
}
if (continueNext) continue;
result++;
}
return result;
}
private (IList < char> keys, IList<int> counts) CountString(string str)
{
var keys = new List();
var counts = new List<int>();
for (int i = 0; i < str.Length; i++)
{
var count = 1;
while (i + 1 < str.Length && str[i] == str[i + 1])
{
count++;
i++;
}
keys.Add(str[i]);
counts.Add(count);
}
return (keys, counts);
}
}
}
Input
s = "zzzzzyyyyy", words = ["zzyy","zy","zyy"]
Output
3