AtCoder Beginner Contest 259 - C - XX to XXX

Time Limit: 2 sec / Memory Limit: 1024 MB

Score : $300$ points

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.

题目大意

你可以在字符串$S$的连续两个相同的字母变成连续且相同的三个字母

通俗地讲，就是$..aa.$能变成$..aaa.$

问你$S$串能否变成$T$

解题思路

用双指针分别记录$S$和$T$处理到了那个字母。（分别记为$locS$和$locT$）

如果$S$和$T$对应的字母相同，则两个指针分别向后移动一位

if (S[locS] == T[locT])
    locS++, locT++;

否则（$S$和$T$对应的元素不同），要想使得$S$变成$T$就需要在$S$中插入一个字母$T[locT]$

要想在$S$的$locS$处插入一个字母$T[locT]$，就需要$S[loc-1]、S[loc-2]$都为$T[locT]$。（因为已知$S[locS] \neq T[locT]$，所以新插入的字母不可能通过$S[locS]、S[locS + 1]$拓展出来）

• 如果$S[loc-1]、S[loc-2]$都为$T[locT]$，就$locT++$（$T$的$locT$已由$S[loc-1]、S[loc-2]$拓展出来）
• 否则，直接输出No并结束即可。

---

AC代码

#include <bits/stdc++.h>
using namespace std;
#define mem(a) memset(a, 0, sizeof(a))
#define dbg(x) cout << #x << " = " << x << endl
#define fi(i, l, r) for (int i = l; i < r; i++)
#define cd(a) scanf("%d", &a)
typedef long long ll;

#define Yes {puts("Yes"); return 0;}
#define No {puts("No"); return 0;}

int main() {
    string s, t;
    cin >> s >> t;
    int locs = 0, loct = 0;
    while (locs < s.size() || loct < t.size()) {
        if (loct >= t.size()) {
            No;
        }
        if (locs < s.size() && s[locs] == t[loct]) {
            locs++, loct++;
        }
        else {
            if (locs - 2 >= 0 && s[locs - 1] == t[loct] && s[locs - 2] == t[loct]) {
                loct++;
            }
            else {
                No;
            }
        }
    }
    if (loct == t.size()) {
        Yes;
    }
    else {
        No;
    }
    return 0;
}

同步发文于CSDN，原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/125700254