The "Expressive Words" problem asks you to determine, given a "target" string S and an array of "words" words, how many words can be stretched to become the target string S.
A word is considered "stretchy" if it can be made equal to S by expanding some of its groups of characters. A group of characters in S can be stretched if it consists of three or more of the same character, and we can add extra instances of that character to the corresponding group in the word.
Constraints:
S.S.S = "heeellooo" and words = ["hello", "hi", "helo"], only "hello" and "helo" are stretchy matches.
At first glance, this problem suggests checking, for each word, whether you can match it to S by adding extra characters. A brute-force solution might try all possible insertions, but that's inefficient and hard to implement.
Instead, notice that both S and each word can be broken down into groups of consecutive characters. For example, "heeellooo" becomes ['h', 'e', 'l', 'o'] with counts [1, 3, 2, 3]. For a word to match, its group sequence and order must be the same, and each group must be "expandable" to match S's group.
The optimization comes from comparing these groups directly instead of manipulating strings. If a group in S is at least 3, we can stretch the corresponding group in the word to match the length in S. If it's less than 3, the group must match exactly.
The core idea is to process both S and each word into sequences of character groups and counts, then compare them group by group.
S, skip it.S's group count is less than 3, it must match exactly with the word's count.S's group count is 3 or more, the word's count can be less (but not more), as we can stretch it.S's, it's impossible.This approach avoids unnecessary computations and leverages the group structure for efficiency.
Let's use S = "heeellooo" and words = ["hello", "hi", "helo"].
First, group S:
Characters: ['h', 'e', 'l', 'o'], Counts: [1, 3, 2, 3]
Now, for each word:
['h', 'e', 'l', 'o'], Counts: [1, 1, 2, 1]['h', 'i']['h', 'e', 'l', 'o'], Counts: [1, 1, 1, 1]Brute-force Approach:
n be the number of words, m be the average length of S and word.This is efficient and suitable for reasonable input sizes.
The key to solving "Expressive Words" efficiently is recognizing the importance of character groups and their counts. By grouping both the target and each word, and comparing group-by-group with clear rules, we avoid brute-force string manipulation and achieve a clean, linear solution. This approach is both simple and elegant, making the problem approachable for programmers at all levels.
class Solution:
def expressiveWords(self, S: str, words: List[str]) -> int:
def group(word):
chars = []
counts = []
i = 0
while i < len(word):
ch = word[i]
cnt = 1
i += 1
while i < len(word) and word[i] == ch:
cnt += 1
i += 1
chars.append(ch)
counts.append(cnt)
return chars, counts
s_chars, s_counts = group(S)
res = 0
for w in words:
w_chars, w_counts = group(w)
if s_chars != w_chars:
continue
ok = True
for sc, wc, s_cnt, w_cnt in zip(s_chars, w_chars, s_counts, w_counts):
if s_cnt < 3:
if s_cnt != w_cnt:
ok = False
break
else:
if w_cnt > s_cnt or w_cnt < 1:
ok = False
break
if ok:
res += 1
return res
class Solution {
public:
vector<pair<char, int>> group(const string& s) {
vector<pair<char, int>> res;
int i = 0, n = s.size();
while (i < n) {
char ch = s[i];
int cnt = 1;
i++;
while (i < n && s[i] == ch) {
cnt++;
i++;
}
res.push_back({ch, cnt});
}
return res;
}
int expressiveWords(string S, vector<string>& words) {
auto s_group = group(S);
int ans = 0;
for (const string& w : words) {
auto w_group = group(w);
if (s_group.size() != w_group.size())
continue;
bool match = true;
for (int i = 0; i < s_group.size(); ++i) {
if (s_group[i].first != w_group[i].first)
match = false;
int sc = s_group[i].second, wc = w_group[i].second;
if (sc < 3) {
if (sc != wc)
match = false;
} else {
if (wc > sc || wc < 1)
match = false;
}
}
if (match)
ans++;
}
return ans;
}
};
class Solution {
private List<Character> groupChars(String s, List<Integer> counts) {
List<Character> chars = new ArrayList<>();
int i = 0, n = s.length();
while (i < n) {
char ch = s.charAt(i);
int cnt = 1;
i++;
while (i < n && s.charAt(i) == ch) {
cnt++;
i++;
}
chars.add(ch);
counts.add(cnt);
}
return chars;
}
public int expressiveWords(String S, String[] words) {
List<Integer> sCounts = new ArrayList<>();
List<Character> sChars = groupChars(S, sCounts);
int res = 0;
for (String w : words) {
List<Integer> wCounts = new ArrayList<>();
List<Character> wChars = groupChars(w, wCounts);
if (!sChars.equals(wChars)) continue;
boolean ok = true;
for (int i = 0; i < sChars.size(); ++i) {
int sc = sCounts.get(i), wc = wCounts.get(i);
if (sc < 3) {
if (sc != wc) {
ok = false;
break;
}
} else {
if (wc > sc || wc < 1) {
ok = false;
break;
}
}
}
if (ok) res++;
}
return res;
}
}
var expressiveWords = function(S, words) {
function group(word) {
let chars = [], counts = [];
let i = 0;
while (i < word.length) {
let ch = word[i];
let cnt = 1;
i++;
while (i < word.length && word[i] === ch) {
cnt++;
i++;
}
chars.push(ch);
counts.push(cnt);
}
return [chars, counts];
}
let [sChars, sCounts] = group(S);
let res = 0;
for (let w of words) {
let [wChars, wCounts] = group(w);
if (sChars.length !== wChars.length) continue;
let ok = true;
for (let i = 0; i < sChars.length; ++i) {
if (sChars[i] !== wChars[i]) {
ok = false;
break;
}
let sc = sCounts[i], wc = wCounts[i];
if (sc < 3) {
if (sc !== wc) {
ok = false;
break;
}
} else {
if (wc > sc || wc < 1) {
ok = false;
break;
}
}
}
if (ok) res++;
}
return res;
};