Solution Explanation for LeetCode 809: Expressive Words

This problem asks us to determine how many words from a given list (words) can be "stretched" to match a target string (s). Stretching involves extending groups of consecutive identical characters in a word to have a length of 3 or more.

Approach

The core idea is to compare the target string s with each word in words by iterating through both simultaneously. We maintain pointers for both strings and check character groups. If a character group in s is stretchable (length >= 3) or has the same length as its counterpart in the word, we can continue the comparison. Otherwise, the word is not stretchy.

Detailed Algorithm

1. check(s, t) function: This helper function compares the target string s with a word t.

   • Length Check: If the length of t exceeds s, it cannot be stretched to match, so we return false.
   • Iteration: We use two pointers, i and j, to iterate over s and t, respectively.
   • Character Group Comparison:
     • If the characters s[i] and t[j] are different, the words don't match, and we return false.
     • If the characters match, we count the lengths (c1 and c2) of their consecutive identical character groups in s and t respectively.
     • Stretchability Check: We verify if the group in s is stretchable:
       • If c1 < c2 (group in s is shorter than in t), it's not stretchable, so return false.
       • If c1 < 3 and c1 != c2 (group in s is shorter than 3 and different from t), it's not stretchable, return false.
     • Pointer Advancement: After a successful comparison, move the pointers i and j to the end of the respective character groups.
   • Completion: If both pointers reach the end of their strings (i == m && j == n), the word t is stretchy, and we return true. Otherwise, return false.

2. Main Function:

   • Iterate through each word t in words.
   • Call check(s, t) to see if it's stretchy.
   • Increment a counter (ans) if check(s, t) returns true.
   • Return the final count ans.

Time and Space Complexity

• Time Complexity: O(n*m + Σwi), where n is the length of s, m is the number of words in words, and wi is the length of each word. The dominant factor is the nested iteration in the check function, which iterates through the characters of both strings.
• Space Complexity: O(1). We only use a constant amount of extra space for pointers and counters.

Code (Python)

def expressiveWords(s, words):
    def check(s, t):
        m, n = len(s), len(t)
        if n > m:
            return False
        i = j = 0
        while i < m and j < n:
            if s[i] != t[j]:
                return False
            k = i
            while k < m and s[k] == s[i]:
                k += 1
            c1 = k - i
            i = k
            k = j
            while k < n and t[k] == t[j]:
                k += 1
            c2 = k - j
            j = k
            if c1 < c2 or (c1 < 3 and c1 != c2):
                return False
        return i == m and j == n
 
    ans = 0
    for t in words:
        if check(s, t):
            ans += 1
    return ans
 

The code in other languages (Java, C++, Go) would follow a very similar structure, implementing the check function and the main loop according to the algorithm described above. The core logic and complexity remain the same across all languages.