Tejav
#809

Expressive Words

Medium
ArrayTwo PointersString
LeetCode ↗

Approaches

💡

Intuition

Time Space

The brute force approach checks each word against the target string by trying to transform the word into the target string directly. This involves comparing each character and counting the groups of characters to see if they can be stretched to match.

⚙️

Algorithm

4 steps
  1. 1Step 1: For each word in the words array, initialize two pointers, one for the target string s and one for the current word.
  2. 2Step 2: Compare characters at both pointers. If they match, move both pointers forward. If they don't match, check if the current character in the word can be stretched to match the character in s.
  3. 3Step 3: If a character in the word is the same as the character in s, check the count of consecutive characters. If the count in the word is less than 3 and does not match the count in s, break out of the loop.
  4. 4Step 4: If you reach the end of both strings and all conditions are satisfied, count this word as stretchy.
solution.py21 lines
1# Full working Python code
2
3def expressiveWords(s, words):
4    def canStretch(s, word):
5        i, j = 0, 0
6        while i < len(s) and j < len(word):
7            if s[i] == word[j]:
8                count_s, count_w = 0, 0
9                while i < len(s) and s[i] == s[i-1]:
10                    count_s += 1
11                    i += 1
12                while j < len(word) and word[j] == word[j-1]:
13                    count_w += 1
14                    j += 1
15                if count_s < count_w or (count_s < 3 and count_s != count_w):
16                    return False
17            else:
18                return False
19        return i == len(s) and j == len(word)
20
21    return sum(canStretch(s, word) for word in words)

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.