## Expressive Words

• Time:O(|words|\max(|\texttt{words[i]}|)
• Space:O(1)

## C++

``````class Solution {
public:
int expressiveWords(string S, vector<string>& words) {
int ans = 0;

for (const string& word : words)
if (isStretchy(S, word))
++ans;

return ans;
}

private:
bool isStretchy(const string& S, const string& word) {
const int n = S.length();
const int m = word.length();

int j = 0;
for (int i = 0; i < n; ++i)
if (j < m && S[i] == word[j])
++j;
else if (i > 1 && S[i] == S[i - 1] && S[i - 1] == S[i - 2])
continue;
else if (0 < i && i + 1 < n && S[i - 1] == S[i] && S[i] == S[i + 1])
continue;
else
return false;

return j == m;
}
};
``````

## JAVA

``````class Solution {
public int expressiveWords(String S, String[] words) {
int ans = 0;

for (final String word : words)
if (isStretchy(S, word))
++ans;

return ans;
}

private boolean isStretchy(final String S, final String word) {
final int n = S.length();
final int m = word.length();

int j = 0;
for (int i = 0; i < n; ++i)
if (j < m && S.charAt(i) == word.charAt(j))
++j;
else if (i > 1 && S.charAt(i) == S.charAt(i - 1) && S.charAt(i - 1) == S.charAt(i - 2))
continue;
else if (0 < i && i + 1 < n &&
S.charAt(i - 1) == S.charAt(i) &&
S.charAt(i) == S.charAt(i + 1))
continue;
else
return false;

return j == m;
}
}
``````

## Python

``````class Solution:
def expressiveWords(self, S: str, words: List[str]) -> int:
def isStretchy(word: str) -> bool:
n = len(S)
m = len(word)

j = 0
for i in range(n):
if j < m and S[i] == word[j]:
j += 1
elif i > 1 and S[i] == S[i - 1] == S[i - 2]:
continue
elif 0 < i < n - 1 and S[i - 1] == S[i] == S[i + 1]:
continue
else:
return False

return j == m

return sum(isStretchy(word) for word in words)
``````