LeetCode Solutions
809. Expressive Words
Time: $O(|words|\max(|\texttt{words[i]}|)$ Space: $O(1)$
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;
}
};
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;
}
}
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)