grid47 Exploring patterns and algorithms
Aug 18, 2024
7 min read
Solution to LeetCode 809: Expressive Words Problem
You are given a string s and a list of query words. Each word in the query list is said to be ‘stretchy’ if it can be transformed into string s by extending groups of adjacent letters. You can extend a group of letters (e.g., ‘a’, ‘bb’, ‘ccc’) as long as its length is at least 3. For example, if s = ‘heeellooo’, you could extend ’e’ and ‘o’ to make ‘hello’ stretchy. Return the number of query strings that can be stretched to become s.
Problem
Approach
Steps
Complexity
Input: You are provided with two inputs: a string s and an array of words. Each word in the array will be checked to see if it can be transformed into s by the described operations.
Example: Input: s = 'aaaabbbb', words = ['ab', 'aaaabbbb', 'aaabbbbb']
Constraints:
• 1 <= s.length, words.length <= 100
• 1 <= words[i].length <= 100
• s and words[i] consist of lowercase letters.
Output: The output should be an integer representing how many words in the query list can be transformed into string s through the described operations.
Example: Output: 2
Constraints:
• The result is an integer count.
Goal: The task is to determine if each word in the query list can be transformed into string s by extending adjacent letter groups according to the given rules.
Steps:
• For each word in the query list, iterate through its characters and compare them to the corresponding characters in s.
• Check if groups of adjacent characters in both the word and s can be extended by applying the transformation rules.
• Count how many words can be transformed into s.
Goal: Ensure the algorithm handles all edge cases and input constraints correctly.
Steps:
• Handle cases where the word is too short to match s.
• Handle cases where the word contains groups that cannot be extended to match s.
Assumptions:
• Words in the query list are non-empty and consist only of lowercase letters.
• The transformation is only possible if groups of characters can be extended by at least 3 characters.
• Input: Input: s = 'heeellooo', words = ['hello', 'hi', 'helo']
• Explanation: The word 'hello' can be stretched by extending 'e' to 'ee' and 'o' to 'ooo' to match s. The word 'hi' cannot be stretched to match s because it doesn't contain any repeated groups. The word 'helo' cannot match s because the group 'll' is not large enough to be extended.
Approach: The approach involves checking if each word can be transformed into string s by matching groups of adjacent characters and applying the extension operation when possible.
Observations:
• We need to check if a word can match s by extending certain groups.
• This requires comparing groups of characters and verifying if they can be expanded as per the given transformation rules.
• We can use a helper function to check if a word is stretchy by comparing character groups.
Steps:
• Iterate over each word in the query list.
• For each word, iterate through its characters and compare them with s character by character.
• Check for matching groups of characters and ensure that they meet the criteria for stretching (at least 3 characters).
• Count how many words can be stretched to match s.
Empty Inputs:
• If s is an empty string, no words can be stretched to match it.
Large Inputs:
• Handle cases where the length of s or the words in the query list is large, ensuring the algorithm runs efficiently.
Special Values:
• If a word contains no repeated characters, it can't be stretched.
Constraints:
• The algorithm must work efficiently even when s and words have the maximum allowed length.
intexpressiveWords(string s, vector<string>& words) {
int res =0;
for(auto&w : words)
if(check(s, w))
res++;
return res;
}
boolcheck(string s, string w) {
int n = s.size(), m = w.size(), j =0;
for(int i =0; i < n; i++)
if(j < m && s[i] == w[j]) j++;
elseif (i >1&& s[i -2] == s[i -1] && s[i -1] == s[i]);
elseif (i >0&& i < n -1&& s[i -1] == s[i] && s[i] == s[i +1]);
elsereturnfalse;
return j == m;
}
