In this guide, you will get 809. Expressive Words LeetCode Solution with the best time and space complexity. The solution to Expressive Words problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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 <= 100
1 <= words[i].length <= 100
s and words[i] consist of lowercase letters.
Complexity Analysis
Time Complexity: O(|words|\max(|\texttt{words[i]}|)
Space Complexity: O(1)
809. Expressive Words LeetCode Solution in 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;
}
}; /* code provided by PROGIEZ */
809. Expressive Words LeetCode Solution in 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;
}
} // code provided by PROGIEZ
809. Expressive Words LeetCode Solution in 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) # code by PROGIEZ
