Score : $300$ points

问题描述

给定两个字符串 $S$ 和 $T$。确定是否可以通过执行以下操作一定次数（可能为零次）来使 $S$ 等于 $T$。

在 $S$ 中任意两个连续相等的字符之间插入一个与这些字符相等的字符。具体步骤如下：

1. 记 $N$ 为当前字符串 $S$ 的长度，即 $S = S_1S_2\ldots S_N$。
2. 选择一个整数 $i$，满足 $1 \leq i \leq N-1$（包含两端点），且 $S_i = S_{i+1}$。（如果没有这样的 $i$，则无需进行任何操作，并立即终止该操作，跳过步骤3。）
3. 在 $S$ 的第 $i$ 个和第 $(i+1)$ 个字符之间插入一个与 $S_i(= S_{i+1})$ 相同的字符副本。现在，$S$ 变为长度为 $N+1$ 的字符串：$S_1S_2\ldots S_i S_i S_{i+1} \ldots S_N$。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

You are given two strings $S$ and $T$. Determine whether it is possible to make $S$ equal $T$ by performing the following operation some number of times (possibly zero).

Between two consecutive equal characters in $S$, insert a character equal to these characters. That is, take the following three steps.

1. Let $N$ be the current length of $S$, and $S = S_1S_2\ldots S_N$.
2. Choose an integer $i$ between $1$ and $N-1$ (inclusive) such that $S_i = S_{i+1}$. (If there is no such $i$, do nothing and terminate the operation now, skipping step 3.)
3. Insert a single copy of the character $S_i(= S_{i+1})$ between the $i$-th and $(i+1)$-th characters of $S$. Now, $S$ is a string of length $N+1$: $S_1S_2\ldots S_i S_i S_{i+1} \ldots S_N$.

Constraints

• Each of $S$ and $T$ is a string of length between $2$ and $2 \times 10^5$ (inclusive) consisting of lowercase English letters.

Input

Input is given from Standard Input in the following format:

$S$

$T$

Output

If it is possible to make $S$ equal $T$, print Yes; otherwise, print No. Note that the judge is case-sensitive.

Sample Input 1

abbaac
abbbbaaac

Sample Output 1

Yes

You can make $S =$ abbaac equal $T =$ abbbbaaac by the following three operations.

• First, insert b between the $2$-nd and $3$-rd characters of $S$. Now, $S =$ abbbaac.
• Next, insert b again between the $2$-nd and $3$-rd characters of $S$. Now, $S =$ abbbbaac.
• Lastly, insert a between the $6$-th and $7$-th characters of $S$. Now, $S =$ abbbbaaac.

Thus, Yes should be printed.

Sample Input 2

xyzz
xyyzz

Sample Output 2

No

No sequence of operations makes $S =$ xyzz equal $T =$ xyyzz. Thus, No should be printed.

update @ 2024/3/10 10:59:26