How can I solve the Expressive Words problem using two-pointer scanning?

You can solve the problem by using two pointers to compare the groups of repeated characters in the given string `s` and each word. The pointers help track the length of each group and ensure the correct number of extensions for matching.

What is the time complexity of solving the Expressive Words problem?

The time complexity is O(n * m), where n is the number of words and m is the average length of the words, due to the two-pointer approach processing each character once.

What does the invariant tracking technique refer to in Expressive Words?

Invariant tracking refers to monitoring the groups of repeated characters in both the target string `s` and each word, ensuring that they match and can be extended according to the given rules.

What are some common mistakes when solving the Expressive Words problem?

Common mistakes include failing to handle edge cases like non-repeating characters or incorrect extension of character groups that don't meet the minimum required size.

How does GhostInterview help with the Expressive Words problem?

GhostInterview helps by guiding you through the two-pointer scanning approach, assisting in invariant tracking, and providing practice scenarios to handle edge cases in your solution.

#809

Medium

auto_awesome双·指针·invariant

LeetCode 题解工作台

情感丰富的文字

有时候人们会用重复写一些字母来表示额外的感受，比如 "hello" -> "heeellooo" , "hi" -> "hiii" 。我们将相邻字母都相同的一串字符定义为相同字母组，例如："h", "eee", "ll", "ooo"。对于一个给定的字符串 S ，如果另一个单词能够通过将一些字母组…

数组双指针字符串

题目描述

有时候人们会用重复写一些字母来表示额外的感受，比如 "hello" -> "heeellooo", "hi" -> "hiii"。我们将相邻字母都相同的一串字符定义为相同字母组，例如："h", "eee", "ll", "ooo"。

对于一个给定的字符串 S ，如果另一个单词能够通过将一些字母组扩张从而使其和 S 相同，我们将这个单词定义为可扩张的（stretchy）。扩张操作定义如下：选择一个字母组（包含字母 c ），然后往其中添加相同的字母 c 使其长度达到 3 或以上。

例如，以 "hello" 为例，我们可以对字母组 "o" 扩张得到 "hellooo"，但是无法以同样的方法得到 "helloo" 因为字母组 "oo" 长度小于 3。此外，我们可以进行另一种扩张 "ll" -> "lllll" 以获得 "helllllooo"。如果 s = "helllllooo"，那么查询词 "hello" 是可扩张的，因为可以对它执行这两种扩张操作使得 query = "hello" -> "hellooo" -> "helllllooo" = s。

输入一组查询单词，输出其中可扩张的单词数量。

示例：

输入： 
s = "heeellooo"
words = ["hello", "hi", "helo"]
输出：1
解释：
我们能通过扩张 "hello" 的 "e" 和 "o" 来得到 "heeellooo"。
我们不能通过扩张 "helo" 来得到 "heeellooo" 因为 "ll" 的长度小于 3 。

提示：

1 <= s.length, words.length <= 100
1 <= words[i].length <= 100
s 和所有在 words 中的单词都只由小写字母组成。

lightbulb

解题思路

方法一：遍历计数 + 双指针

我们可以遍历数组 $\textit{words}$ ，对于数组中的每个单词 $t$ ，判断 $t$ 是否可以通过扩张得到 $s$ ，如果可以，那么答案加一。

因此，问题的关键在于判断单词 $t$ 是否可以通过扩张得到 $s$ 。这里我们通过一个 $\textit{check}(s, t)$ 函数来判断。函数的具体实现逻辑如下：

首先判断 $s$ 和 $t$ 的长度关系，如果 $t$ 的长度大于 $s$ ，直接返回 $\textit{false}$ ；否则，我们用双指针 $i$ 和 $j$ 分别指向 $s$ 和 $t$ ，初始时 $i$ 和 $j$ 的值均为 $0$ 。

如果 $i$ 和 $j$ 指向的字符不同，那么 $t$ 无法通过扩张得到 $s$ ，直接返回 $\textit{false}$ ；否则，我们需要判断 $i$ 指向的字符的连续出现次数 $c_1$ 和 $j$ 指向的字符的连续出现次数 $c_2$ 的关系。如果 $c_1 \lt c_2$ 或者 $c_1 \lt 3$ 并且 $c_1 \neq c_2$ ，那么 $t$ 无法通过扩张得到 $s$ ，直接返回 $\textit{false}$ ；否则，将 $i$ 和 $j$ 分别右移 $c_1$ 和 $c_2$ 次。继续判断。

如果 $i$ 和 $j$ 都到达了字符串的末尾，那么 $t$ 可以通过扩张得到 $s$ ，返回 $\textit{true}$ ，否则返回 $\textit{false}$ 。

时间复杂度 $O(n \times m + \sum_{i=0}^{m-1} w_i)$ ，其中 $n$ 和 $m$ 分别为字符串 $s$ 和数组 $\textit{words}$ 的长度，而 $w_i$ 为数组 $\textit{words}$ 中第 $i$ 个单词的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

class Solution:
    def expressiveWords(self, s: str, words: List[str]) -> int:
        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

        return sum(check(s, t) for t in words)

speed

复杂度分析

指标	值
时间	complexity depends on the number of words and the length of each word. The two-pointer approach ensures that each character is processed only once, making the overall time complexity O(n * m), where n is the number of words and m is the average length of the words. Space complexity is O(1) as no extra space is required aside from the input and output.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Ability to implement two-pointer scanning effectively.
question_mark
Comfort with tracking invariants across two strings during comparison.
question_mark
Understanding of edge cases and how they affect the algorithm.

warning

常见陷阱

外企场景

error
Not correctly handling edge cases where groups of characters do not meet the required size for extension.
error
Incorrectly tracking character groups, leading to false negatives for valid words.
error
Confusing the requirement for extensions with simple character repetition without extension.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Extend the problem to handle case-insensitive strings or strings with mixed characters.
arrow_right_alt
Introduce more complex constraints such as words with non-alphabetical characters.
arrow_right_alt
Change the minimum group extension requirement to a different threshold, such as 2 or 4 characters.

help

常见问题

外企场景

继续练习

#821 字符的最短距离 #942 增减字符串匹配 #1023 驼峰式匹配