# 809. Expressive Words¶

• Time: $O(|words|\max(|\texttt{words[i]}|)$
• Space: $O(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 25 26 27 28 29 30 31 class Solution { public: int expressiveWords(string s, vector& 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; } }; 
  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 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; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 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)